Module 4 · Creating multi-parameter functions · Lesson 5 of 5

Recursion

You just noticed it: n! is really n × (n-1)!. A definition that refers to itself can be written as a function that calls itself — that's recursion. Every recursive function needs two things: a base case that stops it, and a step that moves toward that base case.

Down to the base case, then back up

fact(4) = 4 * fact(3)?

fact(3) = 3 * fact(2)?

fact(2) = 2 * fact(1)?

fact(1) = 1 # base case

Watch what happens above: factorial(4) can't finish until factorial(3) does, which waits on factorial(2), and so on — each call stacked up, paused, waiting. Only when factorial(1) hits the base case do the answers come flowing back up: 1 → 2 → 6 → 24.

Run it yourselfruns in your browser · Python

main.py

The base case is not optional. Forget it — or never move toward it — and the function calls itself forever, until Python gives up with a RecursionError. It's the recursive cousin of the infinite loop.

Run it yourselfruns in your browser · Python

main.py

Recursion can be beautifully concise — Fibonacci in two lines — but it isn't always the right tool. The recursive fib re-solves the same sub-problems endlessly and crawls for large n, where the loop version flies. Reach for recursion when a problem is naturally self-similar — and keep the loop in your back pocket for everything else.