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.
fact = 1
for i in range(1, n+1):
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:
fact = 1
for i=1 in range(1, 6):
1 *= 1
return 1# 2 Iteration:
fact = 1
for i=2 in range(1, 6):
1 *= 2
return 2# 3 Iteration:
fact = 2
for i=3 in range(1, 6):
2 *= 3
return 6# 4 Iteration:
fact = 6
for i=4 in range(1, 6):
6 *= 4
return 24# 5 Iteration:
fact = 24
for i=5 in range(1, 6):
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.
if n <= 1:
return n * factorial_recursion(n-1)
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)
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.
if len(s) == 0:
elif len(s) == 1:
return [s + '_']
return [s[:2]] + split_string_recursion(s[2:])split_string_recursion('amazing')'out: ['am', 'az', 'in', 'g_']'
Reverse a string using recursion:
if len(s) == 0:
return reverse_string_recursive(s[1:]) + s
Create a fibonacci array using recursion.
if n <=2:
return fib_recursive(n-1) + fib_recursive(n-1)