Is call stack always used when running recursive functions

Question

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]

Possible duplicate of [What Is Tail Call Optimization?](http://stackoverflow.com/questions/310974/what-is-tail-call-optimization) — Frédéric Hamidi, Jan 14 '14 at 09:08
@FrédéricHamidi I can't see how that is a duplicate: although this question is indeed about TCO, it is specifically about Python - which *doesn't* do TCO. — Daniel Roseman, Jan 14 '14 at 09:16
@JakobBowyer ....that is the snippet > the input > the output: works fine on my machine! — whytheq, Jan 14 '14 at 09:21

score 2 · Accepted Answer · answered Jan 14 '14 at 09:17

2

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.

answered Jan 14 '14 at 09:17

Daniel Roseman

588,541
66
880
895

+1 The reference added to my OP is useful as this concept is new to me but seems totally relevent. So effectively if a langauge implements it then best to try and avoid using the call stack? – whytheq Jan 14 '14 at 09:23

Is call stack always used when running recursive functions

1 Answers1