# 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:

![Recursion illustration ](https://cdn.hashnode.com/res/hashnode/image/upload/v1763129032793/dc78ed32-f3a3-4897-9fe6-6c0edbc4e407.png align="center")

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](https://github.com/tobi-20/Data-Stuctures-and-Algorithms-/blob/main/recursion.go)

Further Reading: [Grokking Algorithms](https://www.amazon.com/Grokking-Algorithms-illustrated-programmers-curious/dp/1617292230)