Why is there an RecussionError here when each function is terminating immediately?

Question

num=0
def add(n):
    global num
    num+=n
    if n==0:
        return num
    else:
        return add(n-1)

print(add(10000))

My understanding is that for each function call, it returns another function (recursion) and the function which calls "dies" because it has "return"ed something. So there shouldn't be a problem of stack overflow.

But clearly I'm wrong. Where am I wrong?

output
    if n==0:
RecursionError: maximum recursion depth exceeded in comparison

Thank u!

P.S. I know i'd be better off looping for this problem but i just want to understand the concept.

Your understanding of how recursion works at a stack level may need some brushing up. It doesn't "die" until it gets popped from the call stack, which in this case occurs after all 10000 calls. There's a limit to how many elements can be on the stack, which is what is causing your error. Your function doesn't fully `return` until the recursed method finishes calling, but that method doesn't finish returning until *its* recursed method call finishes, and so on — M Z, Jan 11 '21 at 11:31
What you are describing as "it returns another function (recursion) and the function which calls "dies"" is called [Tail Call Elimination](https://en.wikipedia.org/wiki/Tail_call), something that no contemporary Python implementation does. — MisterMiyagi, Jan 11 '21 at 11:36
Does this answer your question? [What is the maximum recursion depth in Python, and how to increase it?](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it) — KillerKode, Jan 11 '21 at 11:39

score 0 · Answer 1 · answered Jan 11 '21 at 11:33

0

This function actually works, it's just that Python stops the program when you exceed a certain recursion limit (about 1000 recursive calls or so). If you test this program with smaller numbers, everything is fine

answered Jan 11 '21 at 11:33

Daniel

487
4
11

MisterMiyagi · Accepted Answer · 2021-01-11T11:47:40.577

The act of "returning a call" as in return add(n-1) is commonly known as a Tail Call. Semantically the result of call is returned, not the call itself. Strict evaluation requires the complete evaluation of the call while the outer call still lives before returning the result. Thus, the function is indeed a nested call of depth n.

This can be shown by forcing a traceback instead of returning a value. As the final call raises, the outer calls still exist:

>>> def trace(n):
...    if n <= 0:
...        raise LookupError("Showing the traceback/callstack")
...    else:
...        return trace(n-1)
... 
>>> trace(2)
Traceback (most recent call last):
  File "...", line 8, in <module>
    trace(2)
  File "...", line 5, in trace
    return trace(n-1)
  File "...", line 5, in trace
    return trace(n-1)
  File "...", line 3, in trace
    raise LookupError("Showing the traceback/callstack")
LookupError: Showing the traceback/callstack

The optimisation of moving this tail call out of the currently executing call is known as Tail Call Elimination. The reference implementation CPython does explicitly not perform Tail Call Elimination to avoid losing traceback information.

score 0 · Answer 3 · answered Jan 11 '21 at 11:39

Python's default recursion limit is 1000. The limit exists because allowing recursion to occur more than 1000 times doesn't exactly make for lightweight code. Check how is the limit of recursion

import sys
print(sys.getrecursionlimit())

Output

Your function works well for the less number. I have checked it to the last of 997.

and change the recursion limit with sys.setrecursionlimit:

sys.setrecursionlimit(1500)

But doing so is dangerous -- the standard limit is a little conservative, but Python stack frames can be quite big.

Python isn't a functional language and tail recursion is not a particularly efficient technique You can go through more details about increasing the limit Also can get the dept of maximum recursion depth in Python

score 0 · Answer 4 · answered Jan 11 '21 at 11:39

If you pass on such a big number(i.e 10000), the function is told to return the add(n-1) if the argument passed to function isn't 0. So it just loops for 10000 times which raises the RecursionError, though if you pass a smaller number(lets say 10) then the Error will no longer be generated.

Why is there an RecussionError here when each function is terminating immediately?

4 Answers4