# Recursion explained with pictures

## “A Picture is Worth 1,500 Words”

Recursion is basically a simple loop but instead of using loops as *while* or *for* the function will call himself indefinitely.

The function will call himself indefinitely if you don’t **put a condition** to stop the recursion at a specific times.

To image, i will take a really basic example for you to understand more easily, so i will take a number **5** and i will increase his value at each time the function call himself and put a condition to **stop the recursion when number is equal to 0, **we will get at the end the sum (5 + 4 + 3 + 2 + 1 + 0 (1))**.**

At first, i give to the function **sum_unit**() the number 5, the function will execute and will put into the **stack.**

**What is a stack ? **is basically a space of memory were static variables are placed into, the allocation is made by the OS and it is not dynamic at all. If i initialize a variable ** int x = 10, **it will placed right into the stack, because this is not a memory allocated. The other way to have variables into stack is to pass variables into functions (as we do), if you want to have a space of memory allocated (in the heap and not in the stack) you need to use malloc() in C. The stack works as a Last-In-First-Out (

**LIFO**)

So now, **n is equal to 5**, n is not equal to 0 so we will return and call the function but we **decrement n, **at the next call, **n will be equal to 4 as below:**

So we let our function calling himself until **n equal to 0**

Now, **n is equal to **0, so the first if of our function is valid, so now the recursion is ended, the function will not call himself more but will at first **return 1 to stop the recursion.**

And this is now the magic happen, the function will roll but in the other way, **0 to 5 ( check green arrow in the stack)**.

At return 1, n is equal to 0, but because we return 1, it will count a this moment, **so 1 + sum_unit(0) = 1.**

Return n + sum_unit(n-1) is called to roll, so n = 1 and sum_unit(1) = 1.

**1 + 1 =2.**

At the next** Return n + sum_unit(n-1)**,

**n**

**is equal now to 2**because the addition before was equal to 2 and it will addition with the value of sum_unit(2) so 2, 2 + 2 = 4.

etc… until the end of the roll is achieved, so sum_unit(5). The function sum_unit will return at the end where you called the function, **16.**

So as you can see now, the **n + of **(**return n + **sum_unit(n-1)) is not yet executed while the recursion, it execute only when the recursion is done and the roll start.

I hope you understand more about this magic concept.