What is Recursion and how to stack it?

Chebbi Mounir
2 min readMar 12, 2021

--

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

4*4*4*4*1

4times->3times->2times->1time->return 1

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.

--

--

Chebbi Mounir
Chebbi Mounir

No responses yet