Recursion , let´s traverse a stack, and back to beginning!

 

Congrats, you have a recursion!

 

One of the best attributes to become a programmer is to optimize the code, your task as proffesional coder is to find all the possible ways to develop a clear and efficient code and recursion is one of the most used methods. 

Things to remember:

• Be able to explain an algorithm in as few words as possible.
• Whiteboarding clearly and as educationally as possible
• Efficient coding that prevents over use of system memory.
• Not abusing loops, a few nested loops are alright, but too much can be messy!

RECURSION

By definition, recursion is:

    The repeated application of a recursive procedure or definition.

 

What? Aren´t there so much recursive words?

Let's work with a more understandable definition, which is the one that programmers normally have.

Recursion refers to a function or procedure that calls itself.

The way this works is a function that within itself, that function is called again.

We will use this function as example to explain what recursion is:

float _pow_recursion(float x, float y)

{

    if (y == 0)

        return (1);

    if (y < 0)

        return (_pow_recursion(x, y + 1) / x);

 

    return (_pow_recursion(x, y - 1) * x);

}

 

At first sight it looks like a regular  function, but looking it more quietly, we can see that inside the function, the same function is called again. 

This is an example of a recursive function. This function receives two floats, x and y and calculates the result of x to the power of y floats, xand yand calculates the result of xto the power of y.

Let´s play with Stacks!

A stack refers to an ordered, organized, “pile” of something. Imagine a stack of Legos. 

LAST OUT

FIRST IN

In a system, the stack refers to a data structure where items are placed in order and  the memory adress is always known because the way that they are stored.

 The “Lego” piece where each subroutine is stored is called a stack frame.

Items are “pushed” into the stack, just as you would a stack of Legos, and “popped” out in the same way. The order is LIFO — meaning Last In, First Out.

This means that the first item to be stacked, is the last one to be removed. In the same way the last one to be added is the first one to be removed.

Let´s dive in recursion again, how this stack is married with recursion?

This means that another instance of the function is called, while the first  one was still running, which means that the first one did not finish  executing.

Functions will be called within each other over and over until the exit case is  reached.

So that´s the meaning of recursion of functions.

Let’s look at that example again:

After looking at the example and understanding how the stack works with recursion, we can now break down the example step by step and understand it.

 

float _pow_recursion(float x, float y)
{
      if (y == 0)
           return (1);
      if (y < 0)
           return (_pow_recursion(x, y + 1) / x);
      return (_pow_recursion(x, y - 1) * x);
}

So, what we know:

·         It is a function that returns a float, it is called _pow_recursion (hint on what it will do), and it receives two floats, x and y.

·         If y equals 0, then the function returns 1.

·         If y is less than zero, the function calls itself again with the same x and adding 1 to y. It will continue to do so until the exit case of y = 0, and then go back to every subroutine and divide by x.

·         If y is bigger than 0, then the function will call itself again with the same x and substracting 1 to y until the exit case of y = 0 is reached and then go back by multiplying by x for every return value in every subroutine that was saved on the stack.

·         The final return value will be the result of x to the power of y.

Let’s focus on a case of two positive values for both x and y. In our case we will work with 2 and 3.

I used Python tutor software to watch the simulation of stack in our example function.

I created a main function to run the program as below:

 

1	#include <stdio.h>
2
3	float _pow_recursion(float x, float y)
4	{
5	if (y == 0)
6	return (1);
7	if (y < 0)
8	return (_pow_recursion(x, y + 1) / x);
9
10	return (_pow_recursion(x, y - 1) * x);
11	}
12
13	int main(void)
14	{
15	int r;
16	r = _pow_recursion(2, 3);
17	printf("%d\n", r);
18	return (0);
19	}

Our main function starts to run from line 13 and is only the representation of _pow_recursion function.

Now after execution i will present the different steps:

Step 1, all the variables, functions and stack are initialized in "0" 

Stack main r int ?

Heap

 

Step 2, _pow_recursion function is initialyzed.

 

Stack main r int ? _pow_recursion x float ? y float ?

Heap

 

Step 3, values for X and Y.

 

Stack main r int ? _pow_recursion x float 2 y float 3

Hea

 

Step 4, first _pow_recursion change in stack (initialize a new pow value)

 

Stack main r int ? _pow_recursion x float 2 y float 3 _pow_recursion x float ? y float ?

Heap

 

Step 5, new value to float (Y)

 

Stack main r int ? _pow_recursion x float 2 y float 3 _pow_recursion x float 2 y float 2

Heap

 

... This recursion (loop) was created until Y value reaches to "0"

 

Stack main r int ? _pow_recursion x float 2 y float 3 _pow_recursion x float 2 y float 2 _pow_recursion x float 2 y float 1 _pow_recursion x float 2 y float 0

Heap

 

Step 7, When Y value reaches 0, the system start to sum the values of x and y giving  "r" as total result.

 

Note: each time that we get the new sumatory, the stack is released from a frame.

...

 

Stack main r int ? _pow_recursion x float 2 y float 3 _pow_recursion x float 2 y float 2 _pow_recursion x float 2 y float 1

Heap

 

As you seee the x = 2 y = 0 frame desappeared, so our LIFO system is running.

 

Check it as example

 

 

In the example we took 2 and 6 as x and y, that´s why the result is r = 64, in our  archive we used 2 and 3, giving the result of  r = 8.

 

Stack main r int 8

Heap

 

This is the recursion in programming,  function that within itself, that function  is called again.