How Recursion Actually Works

Recursion in a concept that is both confusing and intimidating for many — especially for those beginners without a computer science or mathematics background, like myself. However, once you start digging into the underlying concepts, it’s not actually all that hard to grasp! Let’s get into it.

What is recursion?

The concept of recursion is when a problem can be broken down into smaller steps or instances of the same problem. In basic terms, recursion is a function that calls itself. While a normal, non-recursive function will only run once when it is called, a recursive function will run as many times as necessary until it reaches the “base case.”

A recursive function is composed of two parts: a base case and a recursive case. The recursive case is where a function calls itself, and the base case is the condition that prevents the function from entering into an infinite loop.

So how does it work?

Recursion utilizes something called a call stack. When a function is called, it’s sent to the top of the stack. When it is called again recursively (from within the outer function), that is placed on top of the previous call. If the function continues to execute, it’s added to the top each time. When the base case is reached, the previous execution results are retrieved from the stack, from the top down, and the outer functions pick up where they left off. I like to visualize the data structure like this nostalgic blast from the past:

Here’s a practical example that made the concept click for me: The Fibonacci Sequence.

Here’s the problem description from LeetCode to give some context:

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1

F(n) = F(n — 1) + F(n — 2), for n > 1.

Given n, calculate F(n).

Example 1:

Input: n = 2

Output: 1

Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

This is the recursive solution that I came up with:

Let’s break it down.

When fib is executed, and the return statement including the recursive call is reached, the current function is paused, and the context associated with it is saved in memory within the stack. Each time fib is called, the call has its own copy of n that is only accessible within that call. When the nested call executes and is placed on top of the stack, the function will either continue to recurse, or stop once the base case is reached. When the base cases are reached, which would be either 1 or 0, the function will add up the numbers and return the result.

• If n = 4, when the function is initially called, the base case is passed over since 4 > 1, and fib is once again called.
• Since we need to calculate fib of (n-1) as well as (n-2), our stack develops two different branches. In this round, fib(3) needs to be executed, as well as fib(2). Since both 3 and 2 are both greater than one, yet another round of function calls will execute.
• Fib(3) breaks down to fib(2) + fib(1). Fib(2) breaks down into fib(1) + fib(0), both base cases. The fib(2) from the other branch has already reached its base case.
• Now that base cases are reached, the previous functions waiting within the rest of the stack will finally have their pending answers delivered back down the stack where they can finally be executed.
• Once all of the addition is completed, we end up with an answer of 3.

Feel free to copy and paste the problem solution into an editor and play around with different inputs to see how it works.

I’ll also note that anything implemented recursively can technically be implemented iteratively as well. However, the recursive solutions are often much more readable, even if they may be less efficient than the alternative.

Hopefully this has helped deepen your understanding of recursion. Thanks for reading!