How to do recursion with more than limit digit?

Question

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))

Do you have suggestions for other approaches for me to use beside recursion? — Vincent.N, Dec 22 '19 at 12:55
If you are encountering a memory error and your implementation is correct, that almost certainly means you need to change to a non-recursive approach. 10^19 recursion depth is not even remotely possible on any existing computer — Hymns For Disco, Dec 22 '19 at 12:55
Even apart from the recursive limit problem, I doubt that you have the memory to hold `str(recursion(1000000000000000000))` or the time to calculate `recursion(1000000000000000000)`. Using logarithms you can verify that memory involved is infeasibly large. The function that you are trying to compute grows *faster* than any exponential function. — John Coleman, Dec 22 '19 at 13:19

score 2 · Answer 1 · answered Dec 22 '19 at 13:00

2

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.

answered Dec 22 '19 at 13:00

RafalS

5,834
1
20
25

Thanks. I've tried your method but strangely the result is always 1. Do you know why? And plus the program never ends. It doesn't show any output. – Vincent.N Dec 22 '19 at 13:13
1

@Vincent.N The code in this answer simply doesn't always return 1. If that is what you are observing -- check your indentation perhaps. – John Coleman Dec 22 '19 at 13:14
It 'never' ends because looping 1000000000000000000 times takes a lot of time. Add a simple print inside for loop to see how it's doing. – RafalS Dec 22 '19 at 13:16
Thanks, everyone for answering. @JohnColeman sorry that was very stupid of me. I confused the i with 1 and didn't notice of it. – Vincent.N Dec 22 '19 at 13:22
@RafalS I've tried that. That's a lot of numbers and it exceeds my expectation of run time. So I guess these methods are not yet efficient enough. – Vincent.N Dec 22 '19 at 13:22
A quibble: this function only agrees with OP's function for even `n`. – John Coleman Dec 22 '19 at 15:05

score 1 · Answer 2 · answered Dec 22 '19 at 13:29

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.

John Coleman · Answer 3 · 2019-12-23T22:23:18.020

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).

How to do recursion with more than limit digit?

3 Answers3