# Python recursion explained like for a 4 year old.

**What is a recursion?**

According to wikipedia a recursion is defined as:

“…a method of solving a problem where the solution depends on solutions to smaller instances of the same problem”

Let’s try to understand this statement using an example and then draw some conclusions.

# The philosophy behind recursion:

Let’s look at a problem like calculating 5! (factorial). In order to find out the result of 5! we need to calculate:

` 5! = 5 *4 *3 *2 *1`

Equally we can say that:

**5! =** **5 *4!** = *5 *4 *3 *2 *1*

It seems that our factorial problem boils down to a *“problem where the solution depends on solutions to smaller instances of the same problem”*.

If we were to write down the algorithm for this operation it would look like:

`factorial = n * (n -1)!`

# Creating recursion logic with *for loop:*

Recursion and for loop are interchangeble. It seems an intuitive approach to first look at a for loop in action to understand what is going on.

First we will create the *for loop function and then we will brake it down.*

def factorial_loop(n):

fact = 1

for i in range(1, n+1):

fact *=i

return factfactorial_loop(5)'Out: 120'

## Let’s understand what the for loop does.

- The function takes a number n, in our case number 5
- We define range func to start from 1 to n+1 in order to include (5) and discard the 0 because 0 * any number = 0
- We define “fact = 1” for initial value because any number multiplied by 1 remains unchanged (1*1 = 1)
- Inside “
*for loop*” we take previous result and multiply it by the next number (i)

Let’s visualise what happens with each iteration.

# 1 Iteration:

def factorial_loop(5):

fact = 1

for i=1 in range(1, 6):

1 *= 1

return 1# 2 Iteration:

def factorial_loop(5):

fact = 1

for i=2 in range(1, 6):

1 *= 2

return 2# 3 Iteration:

def factorial_loop(5):

fact = 2

for i=3 in range(1, 6):

2 *= 3

return 6# 4 Iteration:

def factorial_loop(5):

fact = 6

for i=4 in range(1, 6):

6 *= 4

return 24# 5 Iteration:

def factorial_loop(5):

fact = 24

for i=5 in range(1, 6):

24*= 5

return 120

# Create the recursion:

Recursion will do the same job as *for loop* however the syntax for recursion is slightly different and may not be very intuitive at first glance but we will break it down step by step.

`def factorial_recursion(n):`

if n <= 1:

return 1

else:

return n * factorial_recursion(n-1)

factorial_recursion(5)

There are a few things to note here.

- IF / ELSE statement… Recursion creates a loop, this loop has to have a condition to stop. For this reason every recursion has an IF / ELSE statement. In our case when
*n*reaches value 1, we return value one and stop the recursion (loop). - In order to create a recursion a function has to call itself. You can see in the
*else:*part of the function. - When the function is calling itself we need to make sure it will reach our base case (n ≤ 1) in order to stop. In our case we decrement n by one Eg: factorial_recursion(n-1)

# Visualising Recursion:

# Example 2:

Split a word into groups of 2 letters. If word has uneven letters, add “_” to the last letter. The output should be a list with groups of two letters of type string.

- Recursion continues until len(s) =1.
- In the solution we start slicing two letters and instruct python to continue untill base case is hit.

def split_string_recursion(s):

if len(s) == 0:

return ''

elif len(s) == 1:

return [s + '_']

else:

return [s[:2]] + split_string_recursion(s[2:])split_string_recursion('amazing')'out: ['am', 'az', 'in', 'g_']'

# Example 3:

Reverse a string using recursion:

`def reverse_string_recursive(s):`

if len(s) == 0:

return ''

else:

return reverse_string_recursive(s[1:]) + s[0]

reverse_string_recursive('amazing')

# Example 4

Create a fibonacci array using recursion.

`def fib_recursive(n):`

if n <=2:

return 1

else:

return fib_recursive(n-1) + fib_recursive(n-1)

fib_recursive(5)