Recursively calling a method for about (2^60)+ times in python

Question

I am having a case where a method should be called recursively for about (2^60) or more number of times

I made successfully up to 2^9 then is caused "maximum recursion depth exceeded in comparison" is there any way to do this

I am trying to change it to a Iterative method

I am using Python Language

Possible duplicate of [Maximum recursion depth?](http://stackoverflow.com/questions/3323001/maximum-recursion-depth) — arewm, Jun 29 '16 at 17:02
What are you trying to do? Because recursively callign it 2^60 is properly not the answer. There are most properly much more effecient ways to go about this — Colourfit, Jun 29 '16 at 17:02
The recursion depth can be overridden, but you're almost guaranteed to run into an OutOfMemory error or something similar after 2^60 calls. You _probably_ want to reframe your approach to whatever you're attempting to solve. — g.d.d.c, Jun 29 '16 at 17:07
Even without the stack size constraints, even *looping* to `2**60` without doing any work in the loop would take centuries. This is never going to work. — user2357112, Jun 29 '16 at 17:13

score 2 · Answer 1 · edited May 23 '17 at 11:58

2

You need to change your function to iterate instead of recurse.
Example:

def recursionSum(n):
    if n==0:
        return 0
    return n + recursionSum(n-1)

def iterativeSum(n):
    sum = 0
    while(n>0):
        sum += n
        n = n-1 # update parameter and loop again
    return sum

You need to do this because even if your function is tail recursive(doesnt maintain a call frame on the stack after it finishes) python doesnt optimize it. So you cannot use long recursive calls in python. Refactor your code to iterate. Provide your code and I can guide you through the process.

EDIT: here is something you can read on tail recursion (What is tail recursion?)

edited May 23 '17 at 11:58

Community

1
1

answered Jun 29 '16 at 17:10

limbo

684
9
18

My function is fairly complex to solve by iteration. It is a Bellman equation. Do you have any other suggestions? – Kartik Jun 29 '16 at 17:16
1

You can rewrite it as iteration, trust me. Or you can use a language that does support tail recursion. However someone made a good point. 2^60+ is huge... it will not stop in your life time. Can you improve the algorithm so it doesn't recurse as much? – limbo Jun 29 '16 at 17:19
Well, I'm not the one who asked the question. But I've tried to convert my function into iteration, without success. I don't know if someone can help me convert it to iteration. Using another language will require conversion of python objects and all that. – Kartik Jun 29 '16 at 17:23
You can post a new question and hopefully someone can help you with the transformation of the function and also maybe some code optimizations. This is a good example where the language choice matters. Sorry for not checking your name initially. – limbo Jun 29 '16 at 17:27

score 1 · Answer 2 · answered Jun 29 '16 at 17:28

As you said you looking at something involving Bellman Equations, I suggest that you look for implementations regarding that.

A quick Google search found this example on GitHub by rncarpio.

I haven't taken a in-depth look at it, but it may give you something to either use, or base your own implementation off of.

score 0 · Answer 3 · edited Jun 20 '20 at 09:12

Python Docs:

sys.setrecursionlimit(limit)
Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python.

The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash. (emphasis mine)

So put sys.setrecursionlimit(n) or however large you need it before your function. As said in the documentation, your platform may set a limit on n. However 2**60 is not attainable in the python interpreter. I therfore suggest you implement your function iteratively instead of recursively.

score 0 · Answer 4 · answered Jun 29 '16 at 17:15

You can try the following:

import sys
sys.setrecursionlimit(n)

where n is a large number. This is a limit set by the interpreter, another limit is set by the OS. Therefore for large n you will see a different error message. 2^60 recursion calls are definitely not attainable.

Recursively calling a method for about (2^60)+ times in python

4 Answers4