What is Recursion and how to stack it?
Recursion: Basic Concept:
In computer programming, recursion is the process in which a function calls itself.
Let’s take this example:
In this code, we calculate the x to the power of y using a recursive algorithm.
The way it works is by multiplying x, y times, each new call to function _pow_recursion decrements y (in case of y >0) or it increments y (in case of y<0).
When y reaches 0, the callings to the function stops, and we multiply by 1.
exp: x = 4, y = 4
Recursive on the stack:
Implementing a recursive process on the stack data structure makes recursivity easier to understand.
for the previous algorithm, let’s take the case where x=3 and y=2, each new call of the _pow_recursion function is “pushed” on the stack, when the “base case” condition is verified (y = 0 in our case) , we “pull” from the stack.