Recursion

Tobi here.

Today we’re talking about recursion. This one won’t be long because recursion isn’t an algorithm per se, it is a problem solving pattern which is used in implementing a variety of algorithms. Some languages like Haskell don’t even bother with loops; they use recursion for everything. Also, note that recursion isn’t always the most efficient way. Sometimes, the simple approach is better.

Before we go on, we need to talk about a data structure called a stack. As the name implies: imagine stacking things on top of each other, books or cards as the case may be. The last thing you put on top is the first thing you take out- This phenomena is called the “last-in, first-out” structure in computer science (The last book you put on top is the first one you remove).

What Happens When You Call A Function

• 1. You call a function (outer function).
• 2. Inside that function, another function is called (inner function).
• 3. The program pauses the outer function at the point of the call.
• 4. The paused outer function is pushed onto the stack.
• 5. The program now starts executing the inner function.
• 6. If the inner function calls another function, the same process repeats :each new call is pushed on top of the stack.
• 7. When the top function finishes, it pops off the stack.
• 8. Its return value is passed down to the function waiting below it on the stack.
• 9. The waiting function resumes execution from where it paused.
• 10. Steps 7–9 continue until all stacked functions have finished executing.

Illustrated below:

Each box represents a function call, holding its own parameter n. When the top box hits the base case factorial(1) = 1, it starts returning values back down the stack:

factorial(1) returns 1 (base case)

factorial(2) returns 2 * 1 = 2

factorial(3) returns 3 *2 = 6

In conclusion, recursion is a function calling itself, structured around a base case and a recursive case, using the stack to keep track of each call. The stack grows as functions call themselves, and unwinds when they return values.

Golang implementation: GitHub

Further Reading: Grokking Algorithms