Recursion refers to a process that repeats itself until it has achieved its goal. This process repeats itself in terms of its own updated version. Commonly, when a process repeats itself, it is called Recursion. ## Programming Definition

In computer science, one has to work with finding optimal solutions to problems that occurred. These problems could range from a simple calculation to building a full-fledged project. For this, computer scientists usually break more significant problems into small portions. Then, they solve those problems to get the final result at the end. Recursion is known to solve small instances of the problem and provide the solution efficiently.

## Importance of Recursion

#### Comparison with loops and iterations

Usually, programmers use iterations to solve programming problems. Iteration means generating a sequence of outcomes. Programmers prefer it to solve a problem where they can find the solution after a few iterations. However, when it comes to solving enormous problems, Recursion plays a vital role in providing a solution in a short time.

Instead of using loops and iterations, Recursion provides sophisticated and straightforward solutions. Using Recursion in programming leads to better strategic thinking and problem-solving techniques. This practice makes the code easy to develop and increases the understandability of the problem.

#### Formation of Pure Functions

Recursion proves helpful in forming Pure Functions. A pure function refers to a function that returns the value according to the input it receives. Using Recursion, one can simplify problems using pure functions in functional programming, where the user requires solutions to more significant problems.

#### Time and space complexity

A recursive function makes things easier by calling itself without being dependent on another function. Hence, it makes code short, comprehensible and helps to develop significantly easy algorithms. Moreover, the time complexity of an algorithm is also reduced by it.

Time complexity refers to the total amount of time a program or an algorithm takes to execute. Recursive functions generally produce equal time complexities in comparison to iterative functions. Resultantly, recursive functions complete tasks in a lesser amount of time. However, in some cases, more function calls and returns increase the function’s time complexity significantly.

The space complexity of the recursive function is directly proportional to its depth, i.e., the number of times it has called itself. Furthermore, as the recursive function calls itself repeatedly, the program adds every function on the top of the stack whenever it makes a new call and removes it when the function returns. Therefore, the stack keeps growing, due to which the space complexity of the recursive function is slightly higher or equal to the other functions.

## Use of Recursion

Recursion is a very commonly used phenomenon in programming. The programmers use it to find solutions to problems that are breakable into similar smaller problems. For instance, they use it in finding the factorial of a provided input. It is also used in numerous algorithms to find the required solution faster such as binary sort, bubble sort, insertion sort, and selection sort.

Additionally, when it comes to solving problems involving graphs and trees, Recursion functions better as it eliminates the risk of using different iterations to visit every node. A recursive function works better at traversing a tree or graph by providing a specific branch or node needed for a solution.

As the recursive functions consume more memory than others, efficient use of call stack in writing a program is essential. The functions where the call stack works smoothly are considered to be efficient while working with Recursion.

## How Recursion operates

As mentioned above, Recursion breaks down the problem into smaller problems and then solves them individually to form a complete solution. Recursion does its work by keeping the following steps functional.

### Base call

The base call is the part of the function where the function stops after executing it. It is the stop sign for a recursive function to indicate that it has solved the individual problems, and it needs to stop now. If the programmer is not very careful in defining the base case, he may write the infinitely running function, which may crash the program.

### Functional working

The functional working refers to a part of the function where it divides the larger problem into smaller sub-problems that need to be solved.

### Recursive call

Recursive call is an essential part of the function. Here the function calls itself again. However, this time the input is the smaller problem formed in the functional working part.

## Example Functions

The following are some basic examples to explain the working of Recursion in coding.

### Power function

The power function takes the two inputs: base and power, and calculates base ^ (power). Before the programmer writes the recursive function, he needs to define the function’s logic cases to understand its proper working.

These are the logic cases for the power function:

• If the power is 0 or less than 0, the function returns 1, called the base condition.
• Otherwise, the function calculates the power using x^y.

### Mathematical definition

The programmers find out the function’s mathematical definition to make the recursive logic of the function. In the cases above, the user decides only to calculate the positive power of the integers. Additionally, the zeroth power of every integer is 1. Moreover, the simple function of calculating the x power of y integer is to multiple y times x. Every time the number is multiplied by itself, the value of x decreases by 1.

Combining the upper cases gives the following mathematical function f(x, y):

```f(x, y) = {1 , x<=0 ; y * f(x-1, y) , x>y}

```

### Recursive algorithm of the function

In the C++ programming context, the user needs to:

• Declare a function with a name, such as p().
• Define its input parameters and their types, i.e., p (int power, int base)
• Define the return type of the function, i.e., int.

Converting the mathematical function into C++ function gives:

```int p(int power , int base)
{
if (power <= 0) {//base case
return 1;
}
else {
return base * p(power -1 , base);
}
}

```

### Dry Run

```Input: 2, 2
Working :
(2 <= 0) false
Return 2 * p (1, 2)
(1 <=0) false
Return 2* p(0,2)
(0 <=0) true
Return 1
Return 2* 1
Return 2 * 2 * 1
Output: 2*2*1 = 4

```

### Factorial function

The factorial function is the function that multiplies the number with all its predecessors, and is denoted by ‘!’. E.g. the factorial of 4 can be expressed as 4! = 4 X 3 X 2 X 1. In other words, x! = x * (x-1) * (x-2) * … 2 * 1.

These are the required logic cases to break the factorial problem:

• If the input integer is 0 or 1, the factorial is 1, which is the base case for this function.
• If the input is a positive integer greater than 1, it multiplies the integer with all the numbers below it.

### Mathematical Definition

Combining the upper cases gives the following mathematical function f(x):

`F(x) = {1 , x=1 or 0 ; x* f(x-1) , x>1}`

### Recursive Algorithm

To write this function in C++, the user needs to:

• Declare a function with a name, such as factorial ().
• Define its input parameters and their types, i.e., factorial (int number)
• Define the return type of the function, i.e., int.

Converting the mathematical function into C++ gives:

```int factorial( int number)
{
if (number == 1) {//base case
return 1;
}
else {
return number * factorial(number - 1);
}
}```

### Dry Run

```Input: 3
Working :
(3 ==1) false
Return 3 * factorial(2)
(2 ==1) false
Return 2* factorial (1)
(1==1) true
Return 1
Return 2 *1
Return 3 * 2 *1
Output: 3*2*1 = 6
```

## Application: Factorial

`Factorial f (x): f(n) = n*f(n-1), the base condition: if n<=1 then f(n) = 1.`

As discussed, recursion aims to segregate the problem into smaller equations till the base condition is implementable. For example, in the above factorial program, it is resolving the factorial function f(n) by calling a reduced factorial function f(n-1); it frequently happens until the n value reaches base condition(f(1)=1). If the user does not explain the base condition in the recursive function, it may show a stack overflow error.

## Memory Allocation

When a user calls a function from main (), the memory is storing in the stack adaptor. The recursive function calls itself. The memory for a called function (storing in a stack) on top of memory allocated to the calling function and various copies of local variables creates for each function call. When it reaches the base condition, the function returns the value to the main function by whom it is getting called, and memory is de-allocated, and the course continues.

```// A C++ program to demonstrate working of
// recursion
#include <bits/stdc++.h>
using namespace std;

void ExampleFunction(int test)
{
if (test < 1)
return;
else {
cout << test << " ";
ExampleFunction(test - 1); // statement 2
cout << test << " ";
return;
}
}```

When ExampleFunction(3) is called from main(), memory is allocated to ExampleFunction(3) and a local variable test is initialized to 3 and declaration 1 to 4 are pushed on the stack adaptor. It first prints ‘3’. In statement 2, ExampleFunction(2) is called and memory is allocated to ExampleFunction(2) a local variable test is initialized to 2 and declaration 1 to 4 are pushed in the stack adaptor. Similarly, ExampleFunction(2) calls ExampleFunction(1) and ExampleFunction(1) calls ExampleFunction(0). ExampleFunction(0) runs through if statement and returns to ExampleFunction(1). Remaining statements of ExampleFunction(1) executes and it returns to ExampleFunction(2) and so on. In the output, result value from 3 to 1 are printed and then 1 to 3 are printed.

## Direct Recursion vs Indirect Recursion

Direct recursion: When a function calls itself, it is called direct recursion. The above example is a direct recursion example.

Indirect recursion: When a function takes the help of another function called the calling function, this is called indirect recursion. For example: ExampleFunction A calls ExampleFunction B and ExampleFunction B calls ExampleFunction A.