Math Applications using Recursion
So far, we have been using the for loops and while loops in programs that need iteration of a section of code several times.
An example of an iterative code is the computation of factorial. The previous section has a program to calculate the factorial using for iterative loops.
In this section, we introduce another method to loop a block of code several times.
The programs that need to execute a block of code several times can use a structure called recursion.
We learned about recursion in the LOGO Recursion chapter.
Let us now see how we can use recursion in Python.
What is recursion?
We know that in Python (and all other languages), a function can call other functions. If a function calls itself within the function itself, the function is called a recursive function.
Putting it another way, a function that is called in its own definition is called a recursive function. Thus, in Recursion a function is defined in terms of itself.
Recursion works like a loop. You can convert any iterative loop to recursion. To explain the recursion, let us use the problem of factorial computation.
Factorial of a number n denoted by n! = n x (n-1) x (n-2) x …x 3 x 2 x 1
By the above definition, factorial of number 1, 1! = 1
2! = 2 x 1. We can write this as 2! = 2 x 1!
3! = 3 x 2 x 1. We can write it as 3! = 3 x 2!
4! = 4 x 3 x 2 x 1. We can write it as 4! = 4 x 3!
Generalizing, n! = n x (n-1)!
Factorial Using Recursion
From the above, we see we defined the factorial of number ‘n’ in terms of the factorial of the number (n-1).
Therefore, knowing the factorial of the number (n-1), we can compute the factorial of the number n by multiplying the number n by the factorial of (n-1). This is the concept of recursion.
Let us write a small program to calculate the factorial of a number n using recursion.
Note that factorial of number 0 = 1.
PROGRAM EXAMPLE: CALCULATE FACTORIAL USING RECURSION
Program Name: recursion_factorial.py
# Simple Recursion Program Example
# Factorial of an integer n
def factorial(n):
if n == 0:
return 1
else:
result = n * factorial(n - 1) # Call function 'factorial' within the function.
print("Factorial of number ", n, " * factorial(",n - 1,"):", result)
return result
print("Factorial of number 0 : ", factorial(0))
factorial(7) # Call function 'factorial'.
The following is the program output.
Python 3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 22:39:24) [MSC v.1916 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>>
Factorial of number 0 : 1
Factorial of number 1 * factorial( 0 ): 1
Factorial of number 2 * factorial( 1 ): 2
Factorial of number 3 * factorial( 2 ): 6
Factorial of number 4 * factorial( 3 ): 24
Factorial of number 5 * factorial( 4 ): 120
Factorial of number 6 * factorial( 5 ): 720
Factorial of number 7 * factorial( 6 ): 5040
>>>
Recursive Function Base Condition
Since a recursive function calls itself, this process would repeat indefinitely if not stopped by some condition. This condition is known as the base condition. Without the base condition, a recursive program will continue to execute forever in an infinite loop.
If the base condition is met, the program executes the instructions and exits the recursive loop. On the other hand, if the base condition is not met, the program executes some code and then calls itself to continue recursion. This process repeats indefinitely until the base condition is met.
for, while Iterative Loops vs. Recursive Loops
From the sections above, we have learned that if you want to repeat a block of code, we use the for and while loops. The for and while loops iterate the code as specified in the range() function or when a condition occurs (while loop).
Recursion structures provide us with another way to repeat a block of code by calling a function within itself to solve a smaller version of the same problem.
To compare the three structures, let us write a program using for loop iterative loop and the while iterative loop structure.
The program below defines a procedure named factorial(n), which is called by the main program.
PROGRAM EXAMPLE: FACTORIAL COMPUTATION USING ITERATIVE for LOOP STRUCTURE
Program Name: Program Name: factorial_for_loop_iterative.py
###### Iterative for loop code structure of factorial computation. ######
def factorial(n):
factorial = 1 # Initialize variable 'factorial'.
if n < 0:
print("factorial of negative number is not defined")
elif n == 0:
print("factorial of number 0 is 1") # Factorial of 0 = 1.
else:
for i in range(1, n+1): # i is the counting variable for loop.
factorial = factorial*i
print("factorial of ", n, "=", factorial)
# Call the function 'factorial'.
factorial (-1)
factorial(0)
factorial(1)
factorial(2)
factorial(3)
factorial(4)
factorial(5)
factorial(6)
factorial(7)
The following is the program output.
Python 3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 22:39:24) [MSC v.1916 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>>
factorial of negative number is not defined
factorial of number 0 is 1
factorial of 1 = 1
factorial of 2 = 2
factorial of 3 = 6
factorial of 4 = 24
factorial of 5 = 120
factorial of 6 = 720
factorial of 7 = 5040
>>>
Let us now use the while iterative loop to compute factorial of number 7.
PROGRAM EXAMPLE: FACTORIAL USING while LOOP ITERATIVE STRUCTURE
Program Name: factorial_while_loop_iterative
###### Iterative while loop code structure of factorial computation. ######
print("COMPUTE FACTORIAL OF A NUMBER USING while LOOP")
factorial = 1
num = 7
i = 1
while i <= num:
factorial = factorial * i
i = i + 1
print("The factorial of ", num, "is", factorial)
PROGRAM OUTPUT:
Python 3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 22:39:24) [MSC v.1916 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>>
==== RESTART: C:/Users/Python_scripts/factorial_while_loop_iterative.py ===
COMPUTE FACTORIAL OF A NUMBER USING while LOOP
The factorial of 7 is 5040
>>>
Below is a program to compute the sum of numbers using recursion.
Recursion Function to Compute Sum of Numbers
The simple program below computes the sum of a few numbers using a recursive function.
PROGRAM EXAMPLE: RECURSION STRUCTURE TO COMPUTE SUM OF NUMBERS
Program Name: recursion_sum.py
# Recursive method to compute sum of few numbers.
print("USING RECURSION STRUCTURE.")
def sum(n):
if n == 0:
print("The sum of numbers from 0 to",n, "the sum = ",0)
return 0
else:
addition_result = n + sum(n-1)
print("The sum of numbers from 0 to",n, "the sum = ",addition_result)
return addition_result
sum(5)
print()
print("NOW USE THE ITERATIVE STRUCTURE")
# Iterative method to find sum of a few numbers.
sum = 0
for n in range (0,6):
sum = sum + n
print("The sum of numbers from 0 to",n, "the sum = ",sum)
The following is program output.
Python 3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 22:39:24) [MSC v.1916 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>>
USING RECURSION STRUCTURE.
The sum of numbers from 0 to 0 the sum = 0
The sum of numbers from 0 to 1 the sum = 1
The sum of numbers from 0 to 2 the sum = 3
The sum of numbers from 0 to 3 the sum = 6
The sum of numbers from 0 to 4 the sum = 10
The sum of numbers from 0 to 5 the sum = 15
NOW USE THE ITERATIVE STRUCTURE
The sum of numbers from 0 to 0 the sum = 0
The sum of numbers from 0 to 1 the sum = 1
The sum of numbers from 0 to 2 the sum = 3
The sum of numbers from 0 to 3 the sum = 6
The sum of numbers from 0 to 4 the sum = 10
The sum of numbers from 0 to 5 the sum = 15
>>>
To compare the iterative and the recursive techniques, we will generate a sequence of numbers known as the Fibonacci Sequence.
First, let’s review what the Fibonacci Sequence is.
Fibonacci Sequence
Fibonacci Series is a series of numbers in which each number of the series is a sum of the previous two numbers of the series.
https://en.wikipedia.org/wiki/Fibonacci_number
For example, if the first two numbers of the series are 1 and 2 the third number is equal to 1 + 2, which is 3.
So, the series becomes 1, 2, 3.
The next number in the series is 2 + 3, which is 5.
So, the series now becomes 1, 2, 3, 5.
The next number is 3 + 5, which is 8.
The next number is 5 + 8, which is 13.
So, the Fibonacci series now becomes 1, 2, 3, 5, 8, 13….. and so on.
Fibonacci Sequence Algorithm
The Fibonacci Sequence algorithm is as follows.
If a and b are two consecutive numbers of the Fibonacci sequence, then the next two numbers are given by the following assignment statement #1 below. As a result of this statement, ‘b’ on the right-hand side of the = symbol replaces ‘a’ on the left-hand side and ‘a+b’ on the right-hand side of the = symbol replaces ‘b’ on the left-hand side. So, the series becomes, a, b, a+b.
a, b = b, a+b # 1
We repeat the above statement in a loop using the while loop.
Note the above statement to generate the Fibonacci series must be written on one line as above, instead of two lines as shown in 2) below.
a = b
b = a + b # 2
Code line 1): The statement a, b = b, a + b, the right side is evaluated together and then assigned to variables ‘a’ and ‘b’ on the left-hand side of the assignment statement.
Code line 2): If the statement is written on two lines, the evaluation is done sequentially and the result will come out wrong. Try it and see if you get the correct result.
Fibonacci Sequence Using Python
In the LOGO Recursion chapter, we used LOGO to create Fibonacci Numbers. In the following program, we generate the first few numbers less than 30 of the Fibonacci Series first using a while loop, and then using a recursive function.
PROGRAM EXAMPLE: CALCULATE FIBONACCI SEQUENCE USING ITERATIVE STRUCTURE
>>> # Define variables 'a' and 'b' as the first member of Fibonacci series.
>>> # initialize a = 1 and b = 1
>>> a = 1
>>> b = 1
>>> while a < 30:
print(a)
a, b = b, a + b
>>> # Evaluate right side simultaneously for b and a + b first
>>> # before the assignment of the values to the left-hand side variables.
>>> # The value of right-hand side 'b' is assigned to left-hand side 'a'.
>>> # and value of right-hand side a + b is assigned to left-hand side 'b'.
>>> # The sum of two adjacent number defines the next number
>>> # of the Fibonacci series.
1
1
2
3
5
8
13
21
>>>Fibonacci Sequence Using Recursive Structure
In the last section, we used the while iterative loop to generate the Fibonacci Sequence.
Let us now create the Fibonacci sequence using recursion.
PROGRAM EXAMPLE: FIBONACCI SEQUENCE – RECURSIVE FUNCTION
Program Name: Recursion_fibonacci
# RECURSIVE FUNCTION TO CREATE FIBONACCI SEQUENCE.
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1 # The first Fibonacci number is 1.
else:
return fibonacci(n-1) + fibonacci(n-2)
# The next Fibonacci number is created by adding the previous two Fibonacci numbers.
print("THE FIRST TEN Fibonacci NUMBERS ARE:")
for i in range(1,11):
print(i," ", fibonacci(i))
The following is the program output.
Python 3.8.1 (tags/v3.8.1:1b293b6, Dec 18 2019, 22:39:24) [MSC v.1916 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>>
THE FIRST TEN Fibonacci NUMBERS ARE:
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
>>>
Fibonacci Numbers and Golden Ratio
Fibonacci numbers are said to have a golden ratio. The golden ratio is defined as the result of the division of any number of the series by the immediately preceding number of the series.
If you take any two consecutive numbers in a Fibonacci sequence and divide the larger number by the smaller number, the result is approximately 1.6. This is true for any two consecutive numbers in a Fibonacci sequence. This is called the ‘golden ratio’.
Let us write a program to calculate the golden ratio of Fibonacci numbers.
The following program calculates Fibonacci numbers as we did in the previous example. The program then divides the larger Fibonacci number by the immediately preceding Fibonacci number. As the numbers get larger, the ratio approaches 1.6.
PROGRAM EXAMPLE: FIBONACCI NUMBERS AND THE GOLDEN RATIO
>>> # Create Fibonacci numbers and calculate golden ratio
>>> a = 1
>>> b = 1
>>> while a < 100:
print('Fibonacci number =', a, 'Golden ratio =',b/a)
a, b = b, a + b # Calculate Fibonacci numbers
Fibonacci number = 1 Golden ratio = 1.0
Fibonacci number = 1 Golden ratio = 2.0
Fibonacci number = 2 Golden ratio = 1.5
Fibonacci number = 3 Golden ratio = 1.6666666666666667
Fibonacci number = 5 Golden ratio = 1.6
Fibonacci number = 8 Golden ratio = 1.625
Fibonacci number = 13 Golden ratio = 1.6153846153846154
Fibonacci number = 21 Golden ratio = 1.619047619047619
Fibonacci number = 34 Golden ratio = 1.6176470588235294
Fibonacci number = 55 Golden ratio = 1.6181818181818182
Fibonacci number = 89 Golden ratio = 1.6179775280898876
>>>