### Introduction

When we think about repeating a task, we usually think about the `for`

and `while`

loops. These constructs allow us to perform **iteration** over a list, collection, etc.

However, there's another form of repeating a task, in a slightly different manner. By calling a function within itself, to solve a smaller instance of the same problem, we're performing **recursion**.

These functions call themselves until the problem is solved, practically dividing the initial problem to a lot of smaller instances of itself – like for an example, taking small bites of a larger piece of food.

The end goal is to eat the entire plate of hot pockets, you do this by taking a bite over and over. Each bite is a **recursive** action, after which you undertake the same action the next time. You do this for every bite, evaluating that you should take another one to reach the goal, until there are no hot pockets left on your plate.

### What is Recursion?

As stated in the introduction, recursion involves a process calling itself in the definition. A recursive function generally has two components:

- The
**base case**which is a condition that determines when the recursive function should stop - The call to itself

Let's take a look at a small example to demonstrate both components:

```
# Assume that remaining is a positive integer
def hi_recursive(remaining):
# The base case
if remaining == 0:
return
print('hi')
# Call to function, with a reduced remaining count
hi_recursive(remaining - 1)
```

The **base case** for us is if the `remaining`

variable is equal to `0`

i.e. how many remaining "hi" strings we must print. The function simply returns.

After the print statement, we call `hi_recursive`

again but with a reduced remaining value. This is important! If we do not decrease the value of `remaining`

the function will run indefinitely. Generally, when a recursive function calls itself the parameters are changed to be closer to the base case.

Let's visualize how it works when we call `hi_recursive(3)`

:

After the function prints 'hi', it calls itself with a lower value for `remaining`

until it reaches `0`

. At zero, the function returns to where it was called in `hi_recursive(1)`

, which returns to where it was called in `hi_recursive(2)`

and that ultimately returns to where it was called in `hi_recursive(3)`

.

### Why not use a Loop?

All traversal can be handled with loops. Even so, some problems are often easier solved with recursion rather than iteration. A common use case for recursion is tree traversal:

Traversing through nodes and leaves of a tree is usually easier to think about when using recursion. Even though loops and recursion both traverse the tree, they have different purposes – loops are meant to repeat a task whereas recursion is meant to break down a large task into smaller tasks.

Recursion with trees for example fork well because we can process the entire tree by processing smaller parts of the tree individually.

### Examples

The best way to get comfortable with recursion, or any programming concept, is to practice it. Creating recursive functions are straightforward: be sure to include your base case and call the function such that it gets closer to the base case.

#### Sum of a List

Python includes a `sum`

function for lists. The default Python implementation, CPython, uses an indefinite for-loop in C to create those functions (source code here for those interested). Let's see how to do it with recursion:

```
def sum_recursive(nums):
if len(nums) == 0:
return 0
last_num = nums.pop()
return last_num + sum_recursive(nums)
```

The base case is the empty list - the best `sum`

for that is `0`

. Once we handle our base case, we remove the last item of the list. We finally call the `sum_recursive`

function with the reduced list, and we add the number we pulled out into the total.

In a Python interpreter `sum([10, 5, 2])`

and `sum_recursive([10, 5, 2])`

should both give you `17`

.

#### Factorial Numbers

You may recall that a factorial of a positive integer, is the product of all integers preceding it. The following example would make it clearer:

```
5! = 5 x 4 x 3 x 2 x 1 = 120
```

The exclamation mark denotes a factorial, and we see that we multiply `5`

by the product of all the integers from `4`

till `1`

. What if someone enters `0`

? It's widely understood and proven that `0! = 1`

. Now let's create a function like below:

```
def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)
```

We cater for the cases where `1`

or `0`

is entered, and otherwise we multiply the current number by the factorial of the number decreased by `1`

.

A simple verification in your Python interpreter would show that `factorial(5)`

gives you `120`

.

#### Fibonacci Sequence

A Fibonacci sequence is one where each number is the sum of the proceeding two numbers. This sequence makes an assumption that Fibonacci numbers for 0 and 1 are also 0 and 1. The Fibonacci equivalent for 2 would therefore be 1.

Let's see the sequence and their corresponding natural numbers:

```
Integers: 0, 1, 2, 3, 4, 5, 6, 7
Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13
```

We can easily code a function in Python to determine the fibonacci equivalent for any positive integer using recursion:

```
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
```

You can verify it works as expected by checking that `fibonacci(6)`

equals to `8`

.

Now I'd like you to consider another implementation of this function that uses a for loop:

```
def fibonacci_iterative(n):
if n <= 1:
return n
a = 0
b = 1
for i in range(n):
temp = a
a = b
b = b + temp
return a
```

If the integer is less than or equal to 1, then return it. Now that our base case is handled. We continuously add the first number with the second one by storing the first number in a `temp`

variable before we update it.

The output is the same as the first `fibonacci()`

function. This version is faster than the recursive one, as Python implementations are not optimized for recursion but excels with imperative programming. The solution however, is not as easily readable as our first attempt. There lies one of recursion's greatest strengths: *elegance*. Some programming solutions are most naturally solved using recursion.

### Conclusion

Recursion allows us to break a large task down to smaller tasks by repeatedly calling itself. A recursive function requires a base case to stop execution, and the call to itself which gradually leads to the function to the base case. It's commonly used in trees, but other functions can be written with recursion to provide elegant solutions.