Recursion: Functions Calling Themselves
Functions & Control Flow · Coding Fundamentals track
7 min read
In this module
A Function That Calls Itself
A function can call itself. Sounds circular when you first hear it, but this technique — recursion — is one of the most elegant ideas in computing.
The trick is to keep breaking a problem into smaller versions of itself until you reach one so simple the answer is obvious. That simplest version is the base case.
function countdown(n) { if n <= 0 { // base case print("Go!") return } print(n) countdown(n - 1) // recursive call with a smaller problem}
countdown(3)// Output: 3 2 1 Go!Each call to countdown handles one number, then hands the rest off to a fresh call with a smaller value. When n reaches 0, the base case fires and the chain unwinds.
The Two Requirements
Every recursive function needs exactly two things:
- A base case — a condition under which the function stops calling itself and returns a direct answer.
- A recursive case — the function calls itself with a modified input that gets closer to the base case.
Forget the base case and the function will call itself forever, until the call stack runs out of room. Same disease as a loop without an exit condition.
Recursion solves a problem by reducing it to a smaller instance of the same problem. Every recursive function must have a base case (the simple answer) and a recursive case (the step that makes the problem smaller). Without a base case, recursion becomes infinite.
The Classic Example: Factorial
The factorial of a number n (written n!) is the product of all positive integers up to n. It has a natural recursive definition:
- 0! = 1 (base case)
- n! = n * (n-1)! (recursive case)
Push that loop past 12 and the answers turn to nonsense. 13! is 6,227,020,800, too big for a 32-bit int, so the multiplication overflows long before the recursion gets anywhere near the stack limit.
function factorial(n) { if n == 0 { return 1 } return n * factorial(n - 1)}
factorial(5) // 5 * 4 * 3 * 2 * 1 * 1 = 120Let us trace the calls:
factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3) = 5 * 4 * 3 * factorial(2) = 5 * 4 * 3 * 2 * factorial(1) = 5 * 4 * 3 * 2 * 1 * factorial(0) = 5 * 4 * 3 * 2 * 1 * 1 = 120The calls dig deeper until they hit the base case. Then the return values bubble back up the chain, multiplying as they go.
Recursion and the Call Stack
Each recursive call creates a new stack frame, just like any other function call. For factorial(5), there are six frames on the stack at the deepest point:
The animator below plays the whole thing out. Step forward and watch a new factorial frame land on the stack for each call, each with its own n and its own return address, then watch the frames come off one at a time as the results multiply back up. Its version uses n <= 1 as the base case, a common variant, so it stops at factorial(1) and is one frame shallower than the chart above. The answer is still 120.
Call Stack Animator
Deep recursion eats stack memory. Call factorial(10000000) and you'd need ten million stack frames, which sails right past the few megabytes a typical thread gets for its stack and crashes the program with a stack overflow (ignoring, for a moment, that the result overflowed an int long before).
Recursion vs. Iteration
Anything you can do with recursion, you can do with a loop, and the other way round. Here's the iterative version of factorial:
function factorial_iterative(n) { result = 1 for i = 1; i <= n; i = i + 1 { result = result * i } return result}So when should you reach for recursion over iteration?
- Recursion wins when the problem naturally breaks into smaller sub-problems with the same shape: tree traversal, divide-and-conquer algorithms, parsing nested structures.
- Iteration is usually more efficient for simple counting and accumulation, since it doesn't manufacture new stack frames each time round.
Recursion can also hide a lot of repeated work. The textbook Fibonacci function calls itself twice per step, and it recomputes the same values again and again. Guess how many calls fib(30) makes before you run this.
That explosion in calls is exponential growth, and you'll learn to name it properly in the algorithms module.
Tail Recursion
Tail recursion is the special case where the recursive call is the very last thing the function does. No pending work waits after the call returns.
function factorial_tail(n, accumulator) { if n == 0 { return accumulator } return factorial_tail(n - 1, n * accumulator) // tail position}
factorial_tail(5, 1) // 120Some compilers can flatten tail recursion into a plain loop (called tail call optimisation), reusing the same stack frame for every call and dodging the overflow risk entirely. Not all languages guarantee this, but knowing how to write tail-recursive code is worth it when they do.
Real-World Recursion: Tree Traversal
Hierarchical data is recursion's home turf. A file system is a tree: directories contain files and other directories. Listing every file is naturally a recursive description:
function list_all_files(directory) { for item in directory { if item is a file { print(item.name) } else if item is a directory { list_all_files(item) // recurse into subdirectory } }}Doing this iteratively means hand-rolling a stack data structure to track which directories still need visiting. The recursive version mirrors the data's shape directly.
The Bigger Picture
Recursion is a way of thinking, not just a programming trick. Sorting, searching, parsing, graph traversal — huge swathes of computer science have elegant recursive solutions. When a problem can be defined in terms of smaller instances of itself, recursion is the natural tool.
Recursion also sharpens your mental model of the call stack, stack frames, and function calls at the machine level. That mental model becomes load-bearing once you reach assembly language and exploitation later in this curriculum.