L3·Functions & Modules

🔁Recursion

Functions that call themselves — base case, recursive case, call stack.

recursionstackbase casememoization

§ 1Two parts

Every recursive function needs a base case (stop) and a recursive case that moves toward it. Missing the base case causes RecursionError.

§ 2The call stack

Each call gets its own frame with its own local variables. Frames stack up until the base case returns, then unwind. Python's default limit is about 1000 frames.

§ 3Memoization

Cache results of repeated sub-calls with functools.lru_cache — turns exponential fib into linear.

1from functools import lru_cache​
2@lru_cache​
3def fib(n):​
4 return n if n < 2 else fib(n-1) + fib(n-2)​

Worked example

1def fact(n):​
2 if n <= 1:​
3 return 1​
4 return n * fact(n - 1)​
5​
6print(fact(4))​

Try it live · Python runs in your browser

Loading playground…
ChallengeWrite a recursive function that sums the digits of a number.

Checkpoint quiz

Question 1 / 2
Without a base case you get:

Lesson test

Take an 8-question test on “Recursion” — concepts, output prediction, bug spotting and interview questions.