Recursion is a concept that is extensively used in mathematics and computer science.
Recursion can also be perceived as that act of defining a function in terms of itself.
A recursive function is a function that calls itself until a base condition is met.
TIP steps through a recursive function with pen and paper to get a better understanding of how things work under the hood.
There are 2 important things I want to emphasize in the above definitions.
- The base case.
- Defining a function in terms of itself (Recursive Case).
There is also a data structure that plays a vital role when using recursion it is called the CALL STACK.
The CALL STACK uses LIFO(Last In First Out) as a method of processing data such that the first item to enter into it is always the last to come out of it. To understand the CALL STACK imagine pancakes that are stacked on top of each other to be served.
To get to the last pancake, the pancake at the top has to be served first. Hence this can be seen as mimicking the LIFO data processing technique. The last pancake to get in is the first to get served.
A recursive function has two cases the base and the recursive case. The recursive case makes sure that the function calls itself but with the original argument reduced in some form until it reaches the base case. So for every call to itself, the original argument is reduced by a certain quantity until it reaches the base case.
Recursion is essentially a function calling itself, but the function needs to stop calling itself at some point if a condition is met else we will run into an infinite loop. The condition at which the function should stop calling itself is referred to as the base case. And for every recursive function, there must be at least one base case.
Consider the following example.
5 * factorial(5–1) which is 5 * factorial(4) ====> push onto the stack (STACK ITEM A);
4 * factorial(4 -1); 4 * factorial (3) push onto the stack (STACK ITEM B);
3 * factorial(2); push onto the stack (STACK C);
2 * factorial(1); pushed onto the stack (STACK D);
1 * factorial(0); pushed onto the stack (STACK E);
But our base case carefully handles the case where n === 0; by returning 1;
And remember that the CALL STACK is (LIFO) hence we can say
STACK E, STACK D, STACK C …is the order of execution.
Hence the result of calling the function with the given arguments is evaluated from the last item to get to the stack to the very first.
STACK E: 1 * 1;STACK D: 2 * 1 * 1;STACK C: 3 * 2 * 1 * 1;STACK B: 4 * 3 * 2 * 1 * 1;STACK A: 5 * 4 * 3 * 2 * 1 * 1;
Thanks for reading.