TwiddleLab / Courses / Code

Recursion: Functions That Call Themselves

Functions that call themselves: watch call trees grow, draw fractals and solve mazes.

Intermediate · 11 lessons · Free, no account needed

Best after: Build with Python, Algorithms in Motion

Start the course

Lessons

1. A Function That Calls Itself (5 min): Recursion is a function that calls itself on a smaller version of the job.
2. The Base Case (7 min): The base case is the line that answers without calling again. It is the floor.
3. Trust the Smaller Problem (7 min): Recursive thinking: do one small piece yourself and trust a smaller call with the rest.
4. Trees of Calls (7 min): A function that calls itself twice makes a call tree: every circle is one call.
5. Remember Answers: Memoization (7 min): Memoization: keep a notebook of answers. Before working something out, look it up; after, write it down.
6. Towers of Hanoi (7 min): A recursive plan: to move n disks, move n - 1 out of the way, move the biggest, then move the n - 1 back on top.
7. Drawing Fractals (7 min): A fractal is a shape made of smaller copies of itself: a tree is a trunk with two smaller trees on top.
8. Divide and Conquer (7 min): Divide and conquer: split the problem into smaller parts, solve each part with the same function, combine the answers.
9. Generate Everything: Subsets and Orders (7 min): Brute force: list every possibility and check each one.
10. Backtracking: Solving a Maze (7 min): Backtracking: try a choice and go deeper; at a dead end, undo the last choice and try the next one.
11. Sudoku Solver (7 min): A constraint is a rule every answer must keep: no digit twice in a row, column or box.

Lessons are interactive and need JavaScript. Turn it on to play them.