Lesson 2 · Foundations

Recursion and the Call Stack

Recursion solves a problem by solving smaller instances of the same problem. It relies on the call stack to pause the current function, resolve the subproblem, and resume.

The concept of recursion

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. In programming, this means a function calls itself.

Instead of using a loop to iterate through data, a recursive function processes one piece of data, and delegates the rest of the work to a recursive call.

A function that calls itself
Breaks problems down into identical subproblems
Often results in cleaner, more mathematical code

Base case and recursive case

Every recursive function must have two parts: the base case and the recursive case. The base case is the simplest, smallest instance of the problem that can be answered immediately without further recursion.

The recursive case calls itself with a smaller or simpler input. A base case is not enough by itself: every recursive path must move toward and eventually reach it, or calls continue until the runtime exhausts its call stack.

Base case: When to stop and return
Recursive case: How to shrink the problem
Missing base cases cause infinite loops

Key reference

Terms, operations, and practical uses

Core vocabulary

Recursive callA function invoking itself with a modified input.
Base caseThe condition that stops the recursion and returns a concrete value.
Call stackThe internal memory structure that pauses functions and resumes them in LIFO order.

Performance

Stack OverflowA fatal error caused by recursing too deeply and exhausting available memory.
Tail recursionWhen the recursive call is the final action, allowing the compiler to reuse the current stack frame.
MemoizationCaching the results of recursive calls to avoid repeating identical work.

Practical uses

Tree traversalVisiting every node in a branching structure naturally matches recursion's shape.
Divide and conquerSplitting an array in half (like Merge Sort) and recursively sorting both halves.
BacktrackingExploring choices in a maze or combination lock, and returning when a dead-end is found.

Code example

Calculate factorial recursively

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
print(factorial(4))

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

static int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Inputn = 4

Output24

Example

Run the example step by step

Output

The Call Stack

When a function calls itself, the computer must pause the current function and remember where it left off. It stores this state—local variables and the return address—in a data structure called the Call Stack.

Each paused function is a 'stack frame'. When the base case is finally reached, it returns a value, and the stack unwinds, resuming and completing each paused frame from the top down.

Stack frames store local variables
LIFO (Last-In, First-Out) resolution order
Deep recursion can cause a Stack Overflow

The recursive leap of faith

Tracing a recursive function frame by frame can quickly become confusing. Instead, experienced programmers use the 'leap of faith'.

Assume that your recursive call automatically returns the correct answer for the smaller subproblem. Your only job is to combine that correct sub-answer with the current step's work.

Assume the recursive call works correctly
Focus on the current frame's logic
Ensure the input shrinks toward the base case

Recursion vs. Iteration

A recursive computation can be simulated iteratively, sometimes with a loop alone and sometimes with an explicit stack. A simple linear loop may use O(1) auxiliary space, but iterative tree, graph, and backtracking algorithms can require the same O(h) or O(N) stack space as recursion.

However, recursion is often much more intuitive for non-linear structures like Trees and Graphs, or when exploring combinations and permutations in Backtracking.

Iteration uses loops and O(1) space
Recursion uses O(N) call stack space
Recursion shines in tree traversals and divide-and-conquer

Tail Recursion

If the recursive call is the very last operation performed in a function (with no further math or combination to do), it is called tail-recursive.

Tail-call optimisation can reuse the current frame and make such a call consume O(1) stack space, but the language and compiler must actually perform it. Python does not optimise tail calls, Java does not guarantee it, and a C++ compiler may optimise a tail call but portable code cannot rely on that behaviour.

Recursive call is the absolute last step
Can be optimized by some compilers to O(1) space
Often requires passing an 'accumulator' parameter