Tail Calls and Loops
Recursion: lesson 7 of 8
When nothing happens after the call, the frame is dead weight.
Lesson 7 of 8 · 6 min
Tail Calls and Loops
Step 1 of 12
total(n, acc) adds n to the accumulator and calls itself. The call is the last thing it does.
The Idea
If a recursive call is the very last thing a function does, the caller's frame has no work left. Its locals are never read again.
Some languages spot that and reuse the frame. Python does not, so the stack grows until it hits the limit. The fix is mechanical: the accumulator parameter becomes a variable, the call becomes a loop.
Real-World Example
Handing a clipboard down a line of inspectors, each adding a number and passing it on. Nobody needs to hear back, so nobody needs to stay — the last inspector could have walked the line alone.
The Code
import sys
def total(n, acc=0): # tail call: nothing happens after the call returns
if n == 0: return acc
return total(n - 1, acc + n) # ...so this frame has no work left to come back to
def total_loop(n): # the same function with the frames taken out
acc = 0
while n:
acc, n = acc + n, n - 1 # the accumulator is just a variable now
return acc
print(total(500), total_loop(500)) # 125250 125250
print(sys.getrecursionlimit()) # 1000 -- Python keeps every frame
try: total(100_000)
except RecursionError: print("RecursionError") # the loop version would shrugYour turn
Fill in the blank.
def total(n, acc=0):
if n == 0: return acc
return total(n - 1, acc + n)
def total_loop(n):
acc = 0
while n:
acc, n = ___
return acc
print(total(100) == total_loop(100)) # should print TrueMini quiz
1 / 3