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.
