The concept of recursion

Hello in this blog we are going to explain the concept of recursion.

Well, recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem.

A recursive function is a function that calls itself until a “base condition” is true, and execution stops.While false, we will keep placing execution contexts on top of the stack. This may happen until we have a “stack overflow”. A stack overflow is when we run out of memory to hold items in the stack.

In general, a recursive function has at least two parts:

A base case that makes the recursive function stop and at least one recursive case.

What happen when we call a function recursively?

When a program calls a function recursively, each call to that function is added to the stack. In computer science, the stack is an abstract data structure with two fundamental actions, pushing and popping. The stack is a LIFO structure, which stands for Last In First Out. You can think of a stack of plates at a restaurant. The last plate that was put on the stack is the first plate to be taken off and used. Pushing is the act of adding a layer to the stack, and popping is the act of taking that topmost later off.

Let’s see some examples:

The Factorial function:

int fact(int n)
{
    if (n < = 1) // base case
        return 1;
    else    
        return n*fact(n-1);    
}

Let’s try to find 4!.

The base case:

If the parameter passed is less or equals to 1, we will exit and return 1.

• The recursive case:

If the parameter is not 0 or 1, then we will pass value of n times the return value of calling this function again with n — 1 as its argument.

So if we call factorial(0), the function returns 1 and never hits the recursive case.

The same holds for factorial(1).

checking what happened in the stack:

1. The execution stack places factorial() with 4 as the argument passed. The base case is false, so enter the recursive condition.
2. The execution stack places factorial() a second time with n-1 = 3 as argument. Base case is false, enter recursive condition.
3. The execution stack places factorial() a third time with n-1 (3–1) = 2 as argument. Base case is false, enter recursive condition.
4. The execution stack places factorial() a fifth time with n-1 (2–1) = 1 as argument. Now the base case is true, so return 1.

At this point, we have decreased the argument by one on each function call until we reach a condition to return 1.

6. From here the last execution context completes, n == 1, so that function returns 1.

7. Next n == 2, so the return value is 2. (1×2).

8. Next n == 3, so the return value is 6, (2×3).

So far we have 1×2×3.

9. Finally, n == 4, (4x6) and we have 24 as the final value.

Power function with recursion:

float _pow_recursion(float x, float y)
{
    if (y == 0) //base case
        return (1);
    if (y < 0)
        return (_pow_recursion(x, y + 1) / x);

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

Here, we have a recursive power function called _pow_recursion which takes two integers, x and y, and returns an integer which is the result of x ^ y (x to the power of y).

Let’s check the _pow_recursion of x = 2 and y = 2 ==>

_pow_recursion(2, 2)

The first two if statements are called base cases and are very important. In recursion, a base case returns a value without making subsequent calls to itself. If we called this function like such:

 pow(2, 2); /* 2 to the 2nd power is 4 */

Our pow function will make repeated calls to itself, each time decrementing the variable y until the exponent or variable y reaches the value 0. As you can see, each function call adds another layer to the stack as pictured above. The order in which the stack grows in terms of color is red, orange, then lastly green. Once we reach the green stack call to pow(2, 0), the variable y fulfills the base case condition of if (y == 0). pow(2, 0) returns the value 1 into the previous stack call — pow(2, 1) and pops off the stack.

Once we meet the base case, the fun begins, and each call to the stack will return a value to the previous call that has been waiting for a return value.

When we reach the final red function call, all of the recursive calls to the pow function have returned, and the pow function ultimately returns the value 4. The stack is now empty and our function is complete!