Recursion Basics
📚 What is Recursion? Recursion is when a function calls itself to solve a smaller version of the same problem. It keeps calling itself with smaller inputs until it hits a base case - the stopping condition. Recursion sounds mind-bending at first but it is a powerful technique for problems that nat…
Appy Says…
Recursion sounds scary but it's actually a beautiful idea: a function that calls itself. It's how you solve problems that naturally break into smaller copies of the same problem — like folders inside folders, or a family tree going back generations.
What is Recursion?
A recursive function is one that calls itself with a smaller version of the problem. Every recursive function needs two things: a base case (when to stop) and a recursive case (the self-call that moves toward the base case).
- •Base case: the simplest possible input, where the answer is returned directly
- •Recursive case: break the problem down and call the function with a smaller input
- •Classic example:
factorial(n)—n! = n × (n-1)!, and0! = 1 - •Each call is added to the call stack — Python has a default limit of ~1000 calls
- •Tree traversal, folder scanning, and sorting algorithms like merge sort use recursion naturally
- •If you forget the base case, you get infinite recursion →
RecursionError
Think of it like Russian nesting dolls
A Matryoshka doll contains a smaller version of itself, which contains an even smaller one, until you reach the tiniest doll that doesn't open. Recursion works the same way — each call contains a smaller version of the problem, until you hit the base case (the tiny doll) and start returning answers back up.
How It Works
- •1. Function is called with input
n - •2. If
nmatches the base case — return the answer directly - •3. Otherwise — call the function again with a smaller input (e.g.
n - 1) - •4. Each call waits on the call stack while the inner call runs
- •5. The innermost call hits the base case and returns
- •6. Results bubble back up through each waiting call until the first call gets its answer
Real-World Examples
- •Scanning all files in a folder and its sub-folders (folder inside folder inside folder)
- •Rendering a comment thread where replies have their own replies
- •Building a family tree that goes back through generations
- •The Fibonacci sequence used in financial algorithms and design (Golden Ratio)
- •Merge sort — splits a list in half recursively until single elements, then merges back
Key Facts
- •Python's default recursion limit is 1000 calls — you can raise it with
sys.setrecursionlimit()but this is rarely needed - •Every recursive solution can be rewritten as a loop — sometimes one is clearer than the other
- •Tail recursion (where the recursive call is the last thing) can be optimised by compilers, but Python does not do this optimisation
- •Recursive data structures (trees, graphs) are best processed with recursive functions
Watch Out!
Every recursive function MUST have a base case that is eventually reached. Without one, the function calls itself forever until Python raises RecursionError: maximum recursion depth exceeded. Always ask: 'What's the simplest case I can answer directly?'
Remember
Two parts every recursive function needs: (1) a base case that returns directly, and (2) a recursive call with a smaller input. Missing either one breaks everything.
What You Learned
- •Recursion: a function that calls itself with a smaller input until a base case is reached
- •Must have a base case (stop condition) and move toward it on every call
- •Unlocks: tree traversal, folder scanning, merge sort, comment threads, and any nested-structure problem
Key Facts
- →Python's default recursion limit is 1000 calls — you can raise it with
sys.setrecursionlimit()but this is rarely needed - →Every recursive solution can be rewritten as a loop — sometimes one is clearer than the other
- →Tail recursion (where the recursive call is the last thing) can be optimised by compilers, but Python does not do this optimisation
- →Recursive data structures (trees, graphs) are best processed with recursive functions
Real-World Examples
Remember
Two parts every recursive function needs: (1) a base case that returns directly, and (2) a recursive call with a smaller input. Missing either one breaks everything.
Quick Quiz
Recursion requires?