Reputation: 141
I want to do recursion with the program below but since the input number is too big (19 digits). It throws an error in my program MemoryError: Stack overflow or RecursionError: maximum recursion depth exceeded in comparison. I've tried to reset the recursion limit using
import sys
sys.setrecursionlimit(100000)
But it is not helping. Do you have any solutions to handle this such large number? This is my whole program.
def recursion(n):
return 1 if n < 2 else n * recursion(n - 2)
string = str(recursion(1000000000000000000))
Upvotes: 1
Views: 229
Reputation: 52008
For even n
, your function computes 2*4*6* ... *n
. It is easy to work out that this is the same as 2^(n/2) * (n/2)!
. For example, 2*4*6*8*10 = (2*1)*(2*2)*(2*3)*(2*4)*(2*5)
which is thus 2^5*(1*2*3*4*5) = 32*5!
. This can be quickly an efficiently computed by the function:
import math
def f(n):
k = n//2
return 2**k * math.factorial(k)
For odd n
, it is slightly more complicated. See this question from Math Overflow.
By Stirling's approximation, f(n)
is asymptotically equivalent to sqrt(pi*n)*(n/e)^(n/2)
. Plugging in n = 10^18
, and taking the base-2 log of the result, you can see that f(10^18)
would take roughly 3.6 exabytes to store the resulting integer (which is probably more than your computer can handle).
Upvotes: 0
Reputation: 11
This is one of the practical limitations of recursion without tail call optimization.
Python has a guard against the number of recursive calls you can make in order to avoid a stack overflow. This is the RecursionError
you are seeing:
Python 3.7.4 (default, Aug 13 2019, 20:35:49)
[GCC 7.3.0] :: Anaconda, Inc. on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> def recursion(n):
... return 1 if n < 2 else n * recursion(n - 2)
...
>>>
>>> string = str(recursion(1000000000000000000))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 2, in recursion
File "<stdin>", line 2, in recursion
File "<stdin>", line 2, in recursion
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded in comparison
Increasing is a possible solution, but it only removes the built-in guard. If enough recursive calls are made, you will eventually run out of memory, which is the second error you are getting (MemoryError: Stack overflow
or a segmentation fault in my case).
Python 3.7.4 (default, Aug 13 2019, 20:35:49)
[GCC 7.3.0] :: Anaconda, Inc. on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.setrecursionlimit(100000)
>>> def recursion(n):
... return 1 if n < 2 else n * recursion(n - 2)
...
>>> string = str(recursion(1000000000000000000))
Segmentation fault
The idiomatic solution to this problem in Python would be to use iteration instead:
def iteration(n):
result = 1
for i in range(n, 1, -2):
result *= i
return result
Running this example with your original input (1e18
) won't terminate any time soon though. As the integer grows, it takes increasingly more time to compute, because the operations require using integer representations larger than 64-bit (or however many bits your CPU is able to represent with a single register).
Nevertheless, that would be the Pythonic solution to this problem.
Upvotes: 1
Reputation: 6344
Unfortunately python doesn't optimize tail recursion to iteration. But you can do it yourself:
def recursion(n):
result = 1
for i in range(2, n+1, 2):
result *= i
return result
If you really want it to be recursive then the only thing you can do is to increase recursion limit and stack size, but this is not a good idea.
Upvotes: 2