CODEWITHSUNDEEP
pythonpython-3.xrecursion
Vincent.N
Vincent.N

Reputation: 141

How to do recursion with more than limit digit?

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

Answers (3)

John Coleman
John Coleman

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

filaret
filaret

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

RafalS
RafalS

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

Related Questions