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

that makes the recursive function stop and at least onebase caserecursive 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, thestackis an abstract data structure with two fundamental actions,pushingandpopping. The stack is aLIFO structure, which stands forLast 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.Pushingis the act of adding a layer to the stack, andpoppingis 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:

- The execution stack places
`factorial()`

with 4 as the argument passed. The base case is false, so enter the recursive condition. - The execution stack places
`factorial()`

a second time with`n-1`

= 3 as argument. Base case is false, enter recursive condition. - The execution stack places
`factorial()`

a third time with`n-1`

(3–1) = 2 as argument. Base case is false, enter recursive condition. - 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!