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_cache2@lru_cache3def 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 14 return n * fact(n - 1)56print(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.