CODEWITHSUNDEEP
python
whytheq
whytheq

Reputation: 35557

Is call stack always used when running recursive functions

The following recursive function creates a frame on the call stack and then once the base case is reached all results are popped of the stack:

def subL(L):
    x=len(L)
    if x==1:
        return L
    else:
        subL(L[:x-1])
        print(L[:x-1]) #<<onto the call stack  

>>> j=[2,5,99,31,14,5]
>>> subL(j)

[2]
[2, 5]
[2, 5, 99]
[2, 5, 99, 31]
[2, 5, 99, 31, 14]

I thought all recursive functions used the call stack but does the following? If I place the recursive call at the end of the script then is the call stack not required?

def subLx(L):
    x=len(L)
    if x==1:
        return L
    else:
        print(L[:x-1]) #runs each time it is called so call stack not required?
        subLx(L[:x-1])

>>> q=[2,5,99,31,14,5]
>>> subLx(q)

[2, 5, 99, 31, 14]
[2, 5, 99, 31]
[2, 5, 99]
[2, 5]
[2]

Upvotes: 0

Views: 84

Answers (1)

Daniel Roseman
Daniel Roseman

Reputation: 599610

You are asking about Tail Call Optimization. Python does not do this optimization: all function calls allocate a new stack. That's why it's relatively easy to reach the recursion limit in Python, even with tail calls.

Upvotes: 2

Related Questions