* R*ecursion is a technique by which a function calls itself until a condition is met.

## Introduction

Loops or repetitive execution based on certain conditions are inevitable in programs. Usual loops include `if`

, `while`

and `for`

loops. `Recursion`

is an entirely different way to deal with such situations, and in many cases, easier.

`Recursion`

is a when a function calls itself in each iteration till a condition is met. Ideally, the data set in each iteration gets smaller until it reach the required condition, after which the recursive function exists.

A typical example of recursion is a `factorial`

function.

## How does Recursion work?

A `recursive`

function ideally contains a `Base`

case and a `Recursive`

case.

A `Recursive`

case is when the function calls itself, until the `Base`

case is met. Each level of iteration in the `Recursive`

case moves the control to the next level.

Once a specific level finishes execution, the control is passed back to the previous level of execution. A `Recursive`

function can go several layers deep until the `Base`

condition is met. In short, a `Recursive`

case is a loop in which the function calls itself.

The `Base`

case is required so that the function doesn’t continue running in the `Recursive`

loop forever. Once the `Base`

case is met, the control moves out of the `Recursive`

case, executes the conditions in the `Base`

case (if any), and exits.

As mentioned in the `Introduction`

, a factorial function can be seen as an example of recursion.

### NOTE:

The `Base`

case for a factorial function is when `n == 1`

Consider `n!`

:

`n!`

can be written as:

**n x (n – 1) x (n – 2) x (n – 3) x …. x 1**

`n!`

can also be represented as:

n! = n * (n - 1)! ---> [Step 1] (n - 1)! = (n - 1) * (n - 2)! ---> [Step 2] (n - 2)! = (n - 2) * (n - 3)! ---> [Step 3] . .. ... (n - (n - 1)) = 1 ---> [Base case]

Each level/step is a product of a value and all the levels below it. Hence, `Step 1`

will end up moving to `Step 2`

to get the factorial of elements below it, then to `Step 3`

and so on.

ie.. the control of execution move as:

**[Step 1] -> [Step 2] -> [Step 3] -> ….. [Step n]**

In a much easier-to-grasp example, a `5!`

would be:

5! = 5 * 4! ---> [Step 1] 4! = 4 * 3! ---> [Step 2] 3! = 3 * 2! ---> [Step 3] 2! = 2 * 1! ---> [Step 4] 1! = 1 ---> [Step 5] / [Base case]

The order of execution will be :

**[Step 1] -> [Step 2] -> [Step 3] -> [Step 4] -> [Step 5]**

As we know, in `Recursion`

, each layer pause itself and pass the control to the next level. Once it reach the end or the `Base`

case, it returns the result back to the previous level one by one until it reaches where it started off.

In this example, once the control of execution reaches `Step 5 / Base case`

, the control is returned back to its previous level `Step 4`

. This level returns the result back to `Step 3`

which completes its execution and returns to `Step 2`

, so on and so forth until it reach `Step 1`

.

The return control flow would be as:

**[Base case / Step 5] -> [Step 4] -> [Step 3] -> [Step 2] -> [Step 1] -> Result.**

This can be summed up using an awesome pictorial representation, from the book `Grokking Algorithms`

by Adit. Please check out the `References`

section for the link for more information about this awesome book.

*Figure 1: Recursion, Recursive case and Base case (Copyright Manning Publications, drawn by adit.io)*

## Code

### Example 1:

- A
`factorial`

function in a`while`

loop

def fact(n): factorial = 1 while n > 1: factorial = factorial * n n = n - 1 return factorial print("Factorial of {0} is {1}".format(10, fact(10))) print("Factorial of {0} is {1}".format(20, fact(20)))

- The same function above, in a
`recursive`

loop

def factorial(n): if n == 0: return 1 else: return n * factorial(n - 1) print("Factorial of {0} is {1}".format(10, factorial(10))) print("Factorial of {0} is {1}".format(20, factorial(20)))

### Example 2:

- A function to sum numbers in a normal
`for`

loop.

def my_sum(my_list): num = 0 for i in my_list: num += i return num print(my_sum([10, 23, 14, 12, 11, 94, 20]))

- The same function to add numbers, in a
`recursive`

loop

def my_sum(my_list): if my_list == []: return 0 else: return my_list[0] + my_sum(my_list[1:]) print(my_sum([10, 23, 14, 12, 11, 94, 20]))

## Code explanation

Both `Example 1`

and `Example 2`

are represented as an iterative function as well as a recursive function.

The iterative function calls the `next()`

function on the iterator `sum.__iter__()`

magic method iterate over the entire data set. The recursive function calls itself to reach a base case and return the result.

## Observations:

While a recursive function does not necessarily give you an edge on performance, it is much easier to understand and the code is cleaner.

Recursion has a disadvantage though, for large data sets. Each loop is put on a call stack until it reaches a `Base`

case. Once the `Base`

case is met, the call stack is rewound back to reach where it started, executing each of the previous levels on the way. The examples above showed a `sum`

function and a `factorial`

function. In large data sets, this can lead to a large call stack which in turns take a lot of memory.

## References: