# Recursion

March 21, 2019

Recursion is a very important and powerful idea in computer science and algorithms. A problem can be solved recursively if it can be reduced into smaller similar problems. Recursion is usually implemented by creating **a function which calls itself** from within its own code.

Let us understand this by a simple example of calculating $n!$ (read as ’**n factorial**’).

**Factorial** of a positive integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$. For example, the value of $4!$ is $4\times3\times2\times1 = 24$ . Note that the value of 0! is 1, according to the convention for an empty product.

We can write $n!$ as :

$$ n! = n\times(n-1)\times...\times2\times1 $$This can be written as the following (for $n > 0$):

$$ n! = n\times(n-1)!\ $$For $n=0$, we define $n! = 1$.

Let’s see how we can implement a function `factorial(n)`

which calculates $n!$

```
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n-1); // <== recursion
}
int main() {
cout << "Factorial of 3 is " << factorial(3) << endl;
cout << "Factorial of 1 is " << factorial(1) << endl;
return 0;
}
```

Output:

```
Factorial of 3 is 6
Factorial of 1 is 1
```

The `factorial()`

function above implements the equations we saw earlier quite directly. We’ll take a detailed look at what happens when `factorial(3)`

is called in a bit. First, we want to draw your attention to the following points:

- In the code above, the function
`factorial()`

calls itself in its definition (line 6). This process is called recursion and the function`factorial()`

is a*recursive function*. - The case for $n=0$ is called a
**base case**. Base case is the condition for which we already know the solution (usually a small / trivial case) so as to terminate the recursive calls. Every recursive function must have a base case, otherwise the recursive function will keep calling itself indefinitely forever.

Note: If you are thinking that the above`factorial()`

function can also be implemented iteratively using a single`for`

-loop, then what’s the need of recursion. The main advantage of recursion is that it often simplifies the code, and we will see an example at the end of this tutorial.

# Execution flow of a recursive function

Let us understand the execution flow of the `factorial()`

function you saw earlier.

```
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n-1);
}
int main() {
cout << "Factorial of 3 is:\n" << factorial(3) << endl;
return 0;
}
```

- The execution begins in the
`main()`

function. This calls`factorial(3)`

. - The execution switches to the
`factorial()`

function, with`n = 3`

. - Since
`n == 0`

is not satisfied, we move to`return n * factorial(n-1);`

. This calls the`factorial()`

function again with argument`2`

. (At this point, the execution of`factorial(3)`

function pauses, since it’s waiting for`factorial(2)`

to execute and return.) - The execution switches to the
`factorial()`

function, with`n = 2`

. - Since
`n == 0`

is not satisfied, we move to`return n * factorial(n-1);`

. This calls the`factorial()`

function again with argument`1`

. Again, the execution of`factorial(2)`

function pauses. - The execution switches to the
`factorial()`

function, with`n = 1`

. - Again,
`n == 0`

is not satisfied. This calls the`factorial(0)`

. - The execution switches to the
`factorial()`

function, with`n = 0`

. - Now (finally!),
`n == 0`

*is*satisfied, and the function simply returns 1. - Once
`factorial(0)`

returns,`factorial(1)`

can then continue executing from where it had paused. - It performs
`return 1 * factorial(0)`

, and hence returns 1. (since`factorial(0)`

had returned 1). - Once
`factorial(1)`

has returned,`factorial(2)`

can now continue executing from where it had paused. - It performs
`return 2 * factorial(1)`

, and hence returns 2. (since`factorial(1)`

had returned 1). - Finally,
`factorial(3)`

can now continue executing. It performs`return 3 * factorial(2)`

, and hence returns 6. (since`factorial(2)`

had returned 2). - Now, the main function can continue executing.

Take a moment and go over the above a couple of times to make sure you understand the code execution flow.

To recap, `factorial(3)`

called `factorial(2)`

, which called `factorial(1)`

, and which further called `factorial(0)`

. Because of the `(n == 0)`

check, `factorial(0)`

simply returned 1 instead of making another call to `factorial()`

. Then, `factorial(1)`

could resume execution and return a value, which allowed `factorial(2)`

to resume execution and return, which finally allowed `factorial(3)`

to resume execution and return.

To verify the code execution we just discussed, let’s rearrange our `factorial()`

function a bit and add a `cout`

statement at the beginning and end.

```
int factorial(int n) {
cout << "Starting to calculate " << n << " factorial." << endl; // Statement 1
int result;
if (n == 0)
result = 1;
else
result = n * factorial(n-1);
cout << "Finished calculating " << n << " factorial." << endl; // Statement 2
return result;
}
int main() {
cout << "Factorial of 3 is:\n" << factorial(3) << endl;
return 0;
}
```

This code produces the following output:

```
Factorial of 3 is:
Starting to calculate 3 factorial.
Starting to calculate 2 factorial.
Starting to calculate 1 factorial.
Starting to calculate 0 factorial.
Finished calculating 0 factorial.
Finished calculating 1 factorial.
Finished calculating 2 factorial.
Finished calculating 3 factorial.
6
```

Notice that there is an **equal** number of steps **going** **down** in recursion as **coming up**. Depending on where the statement is written, it will be executed either before or after the recursive call.

The important fact to notice here is that when we make the recursive call, the execution in that function instance **pauses** and only resumes once the **recursive call is executed completely**.

# Importance of base case

You must be careful when writing recursive functions so that we **always reach the base case**. If the code does not encounter the base case, it will go into an *infinite recursion*.

In particular, apart from defining the base case, we also need to ensure that:

- The recursive call should
*not skip*the base case - The base case must be checked
*before*the recursive call

Let’s do an exercise to make sure we understood this well.

# Fibonacci sequence

The Fibonacci sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

The next number in the sequence is the **sum of the two numbers before it**.

The sequence follows the following recurrence:

$$ F(n) = F(n-1)+F(n-2) $$with the base case as $F(0)=0$ and $F(1) = 1$ .

As we know the base case and the recurrence relation, we can write the recursive function for fibonacci as:

```
int fib(int n) {
if (n == 0 || n == 1)
return n;
else
return ( fib(n-1) + fib(n-2) );
}
int main() {
cout << fib(5) << endl;
return 0;
}
```

Let’s see what happens when we call `fib(n)`

.

When we call `fib(n)`

, it calls `fib(n-1)`

and `fib(n-2)`

. `fib(n-1)`

calls `fib(n-2)`

and `fib(n-3)`

. `fib(n-2)`

calls `fib(n-3)`

and `fib(n-4)`

.

The following diagram shows the function calls when `fib(5)`

is called.

The diagram above is called a recursion tree. For each function call, you can see the recursive calls it makes right below it, and the recursive calls those functions make right below them, and so on till the base cases are reached.

Note: The diagram above does not directly show theorderin which the recursive calls are made.

Based on the recursion tree, we can observe that the run-time complexity of finding the above code is **exponential**. To see this, notice that the height of the recursion tree is $O(n)$ and we can see from the left branches that each node calls 2 nodes. Therefore, the complexity is $O(2^n)$.

# Advantages of recursion

In many situations, a recursive implementation is the simplest way to solve a problem.

For example, suppose you have to explore the file system on your computer. The recursive approach to explore your entire file system would be (pseudo-code):

```
define explore(current_folder) {
for each sub_folder in current_folder:
explore(sub_folder)
}
```

# Summary

In this tutorial you learned about:

**Recursion**- a function calling itself**Base case**- the condition at which recursion terminates- base cases must never be skipped
- base case must be checked before the recursive call
- If a recursive function calls itself multiple times, the run-time may become exponential
- In many situation, using recursion greatly simplifies the implementation

# Further reading

- Recursion | Utah
- Merge Sort | CommonLounge: Application of Recursion