In this chapter, we will discuss the concept of Python Recursive Functions. As a prerequisite, you must go through the previous chapters added on Python Functions before reading this post.
Please find here the link to all chapters of Python: Learn Python
Python Recursive Functions
If a function calls itself, it is called a Recursive function. The best way to explain this concept is by discussing about the Factorial. If you want to calculate the factorial of 5, it will be calculated as described below.
factorial(5) = 5*factorial(4)
factorial(4) = 4*factorial(3)
factorial(3) = 3*factorial(2)
factorial(2) = 2*factorial(1)
factorial(1) = 1*factorial(0)
You and I know that the factorial of 0 is 1 and therefore all the prior statements will be assessed and the result will be displayed as mentioned below.
factorial(5) = 5*factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1 * factorial(0)
= 5 * 4 * 3 * 2 * 1 * 1
= 120
Based on the above statements, you can define the formula to calculate the factorial of any number ‘n’ as mentioned below.
factorial(n) = n * factorial(n-1)
Let us now look at a program to find the factorial of any number using recursive functions.
#program to find the factorial
#of any number using recursive functions
def factorialofnum(num):
"""logic to find the factorial of num"""
if num==0:
outcome=1
else:
outcome=num*factorialofnum(num-1)
return outcome
#find factorial of first 15 numbers
for element in range(1,16):
print('Factorial of {} is {}'.format(element,factorialofnum(element)))
Output
Factorial of 1 is 1
Factorial of 2 is 2
Factorial of 3 is 6
Factorial of 4 is 24
Factorial of 5 is 120
Factorial of 6 is 720
Factorial of 7 is 5040
Factorial of 8 is 40320
Factorial of 9 is 362880
Factorial of 10 is 3628800
Factorial of 11 is 39916800
Factorial of 12 is 479001600
Factorial of 13 is 6227020800
Factorial of 14 is 87178291200
Factorial of 15 is 1307674368000
In the program above, you can see that the factorialofnum function was called every time to calculate the factorial of the value in the element variable.
Let us look at one more program using the recursive functions, but this time on the concept of towers of Hanoi.
It is a popular game from China for those of you who don’t know about the Towers of Hanoi. As you can see in the image below, there are three towers A, B, and C. Tower A contains eight disks arranged from smallest disc to most enormous disc. The smallest disc would be at the top, and the enormous disc is placed at the bottom. The agenda of this game is to transfer the discs from tower A to tower C. You can use tower B as the intermediate tower to achieve the same. But the golden rule is that you should never place a giant disc on a small disc, even while moving the discs to tower B.
Please refer to the diagram below to understand the Towers of Hanoi.
#python program with recursive function
#to decipher the towers of hanoi
def towersfunction(num,a,c,b):
if num==1:
#if only one disc, then move it from A to C
print('Move disc %i from tower %s to tower %s'%(num,a,c))
else: #if there's more than one disc
#move num-1 disks from A to B via C as the mediator
towersfunction(num-1,a,b,c)
#move remaining 1 disc from A to C
print('Move disc %i from tower %s to tower %s'%(num,a,c))
#move n-1 discs from B to C using A as the mediator
towersfunction(num-1,b,c,a)
#call the function
num=int(input("Please enter the number of discs: "))
#we should alter n discs from A to C via B as the mediator
towersfunction(num,'A','C','B')
Output
Please enter the number of discs: 3
Move disc 1 from tower A to tower C
Move disc 2 from tower A to tower B
Move disc 1 from tower C to tower B
Move disc 3 from tower A to tower C
Move disc 1 from tower B to tower A
Move disc 2 from tower B to tower C
Move disc 1 from tower A to tower C
As you can see in the program above, complicated concepts such as Towers of Hanoi can be solved easily through recursive functions. If you don’t have recursive functions in complicated concepts like this, the length of the program would be very lengthy.
