>>8,9
It does not trade memory usage for time complexity, it uses the stack implicitly. The call-stack generated at its highest will be the same length as the ``store'' in >>7 which is already really close to the memory use in >>5. You can modify any solution to keep track of how many values are actually skipped and can be discarded. For R(100000), it is 430. It's simply not worth it.