TwiddleLab / Code / Recursion: Functions That Call Themselves
Trust the Smaller Problem
What you will learn
- Recursive thinking: do one small piece yourself and trust a smaller call with the rest.
- You never trace the whole chain in your head. If the smaller call is right, your one step makes the big one right.
- Every chain still needs its floor: the empty list sums to 0, and 0! is 1.
- 5! = 120 is the number of ways to order 5 songs.
How the lesson goes
Add up a list without a loop. A friend helps.
Your friend adds up any shorter list in one go. Cut the list so you do just one addition.
Now the friend is a smaller copy of the same machine.
Each machine keeps the first number and hands the rest to a smaller machine. Feed each slot.
sum_list([3, 1, 4]) = 3 + sum_list([1, 4]) = 3 + 1 + sum_list([4]) = 3 + 1 + 4 + sum_list([]) = 3 + 1 + 4 + 0 = 8. The additions happen on the way back up.
Trust the box: speed round.
The violet box already answered the smaller problem. Don't open it. Finish the big one.
Recursive thinking.
Recursive thinking has three parts. One: do a small piece yourself (the first number, the first letter).
Two: trust the same function to solve the smaller rest. Don't trace it in your head.
Three: a base case for the smallest problem, answered directly: the empty list sums to 0.
Build fact(n) = n x (n - 1) x ... x 1.
Trust fact(n - 1). The floor: fact(0) is 1. Make fact(5) give 120.
fact(n) is n times fact(n - 1): your piece is the multiplication by n, the smaller call does the rest. fact(0) = 1, because returning 0 there would make every product 0.
Run your factorial machine on 5.
Machines open on the way down. Answers come back up.
rev("hello") should give "olleh", but it gives "hello". Fix it.
Trust rev of the rest, then decide where the first letter goes.
The bug put the first letter back in front, so each level undid the reversal. Trusting rev(s[1:]) and adding s[0] at the end reverses the word.
Your factorial counts the ways to order a playlist. When does it pass 1000?
3 songs can play in 6 orders. Slide the number of songs; your fact(n) counts the orders.
Orders of n songs: n choices for the first, n - 1 for the second, down to 1. That product is n!, the same recursion: n! = n x (n - 1)!. 6! = 720 and 7! = 5040.
All these machines are waiting. Which one answers first?
Tap a machine, then Check.
Calls are made top to bottom, but each machine waits for the one below it. Only sum_list([]) can answer without waiting, so answers start at the floor and climb back up.
Previous lesson: The Base Case · Next lesson: Trees of Calls · Part of the course: Recursion: Functions That Call Themselves
Lessons are interactive and need JavaScript. Turn it on to play them.
