Tail carries the answer
When the recursive call is the last action and the result is passed down as an argument, no work waits on the return.
Counting down and up
A simple recursion walks down to the base case, then the answers come back up. Where you do the work, on the way down or on the way back, changes the result.
What you will see
10
About 2 min of reading
Quick check
Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.
Try It
Control the order of work in a recursion.
1
Join rising digits.
def up(n):
if n == 0:
return ""
return up(n - 1) + str(n)
print(up(3))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
123
2
Join falling digits.
def down(n):
if n == 0:
return ""
return str(n) + down(n - 1)
print(down(3))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
321
3
Sum a list on return.
def s(a):
if not a:
return 0
return a[0] + s(a[1:])
print(s([1, 2, 3, 4]))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
10
4
Tail sum with acc.
def t(n, acc):
if n == 0:
return acc
return t(n - 1, acc + n)
print(t(4, 0))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
10
Put it in order
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Data Flow
A simple recursion descends to the base case then returns. Work before the call runs downward; work after the call runs upward.
1
descend to base
↓
2
base returns
↓
3
work on the way back
↓
4
result assembled
Line by line
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
def up(n):
sets nothing on screen
if n == 0:
sets nothing on screen
return ""
sets nothing on screen
return up(n - 1) + str(n)
sets nothing on screen
print(up(3))
123
Why this works
When you have a choice
Down versus up
Doing work before the call runs on the way down; doing it after runs on the way back. The same recursion gives different orders.
Examples
Work on the way back
def up(n):
if n == 0:
return ""
return up(n - 1) + str(n)
print(up(3))The call happens first, then the text. So the numbers join in rising order.
Work on the way down
def down(n):
if n == 0:
return ""
return str(n) + down(n - 1)
print(down(3))The text is added before the call. The numbers join in falling order.
Print while descending
def show(n):
if n == 0:
return
print(n)
show(n - 1)
show(3)Printing before the call shows 3, 2, 1. The calls still nest, but nothing is returned.
Print while ascending
def show(n):
if n == 0:
return
show(n - 1)
print(n)
show(3)Printing after the call shows 1, 2, 3. The print runs as the calls return.
Sum on return
def s(a):
if not a:
return 0
return a[0] + s(a[1:])
print(s([1, 2, 3, 4]))Each frame adds its head after the smaller sum returns. The total builds upward.
Count the calls
def c(n):
if n <= 0:
return 0
return 1 + c(n - 1)
print(c(5))One call per step. The depth of nesting equals the starting number.
Tail shape
def t(n, acc):
if n == 0:
return acc
return t(n - 1, acc + n)
print(t(4, 0))The answer is carried in acc and the call is last. Nothing is added after it returns.
Accumulator avoids build-up
def t(n, acc):
if n == 0:
return acc
return t(n - 1, acc + n)
print(t(10, 0))Passing the running total down means no work waits on the return. That is the tail shape.
Words this lesson uses
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.
← The base case
Previous Lesson
The base case