Recursion

Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive function needs two parts:

• Base case — the condition that stops the recursion (prevents infinite loops)
• Recursive case — where the function calls itself with a simpler input

Think of Russian nesting dolls: you open a doll and find a smaller one inside. You keep opening until you reach the tiniest doll (the base case). Then you close them back up, one by one (the return values flowing back).

Or imagine standing between two mirrors — you see a reflection inside a reflection inside a reflection. Each reflection is a recursive call, and the mirrors' edges are the base case.

Here is a simple countdown example:

function countdown(n):
    if n <= 0:           // Base case
        print("Done!")
        return
    print(n)
    countdown(n - 1)    // Recursive case

Calling countdown(3) prints: 3, 2, 1, Done!

Try it: Countdown from

Factorial is the classic recursion example: n! = n * (n-1) * ... * 1

function factorial(n):
    if n <= 1: return 1       // Base case
    return n * factorial(n-1) // Recursive case

Watch the call stack grow as each call waits for the next, then unwind as return values flow back up.

Fibonacci demonstrates how recursion can branch: each call makes two recursive calls.

function fib(n):
    if n <= 1: return n        // Base case
    return fib(n-1) + fib(n-2) // Two recursive calls!

This creates a tree of calls. Many sub-problems are computed multiple times — notice the redundant (highlighted) nodes!

The call stack is how your computer keeps track of function calls. Each call pushes a frame onto the stack; each return pops it off. Select an algorithm and step through its execution.

Any recursive algorithm can be rewritten as an iterative one (using loops). Compare both approaches side by side and see how the step counts differ.

1. What happens if a recursive function has no base case?

2. What is the time complexity of naive recursive Fibonacci?

3. In the factorial function, what is the base case?