In Python, we know that a function can call other functions. It is even possible for the function to call itself. These types of construct are termed as recursive functions.,Every recursive function must have a base condition that stops the recursion or else the function calls itself infinitely., In this tutorial, you will learn to create a recursive function (a function that calls itself)., Python Functions Python Function Function Argument Python Recursion Anonymous Function Global, Local and Nonlocal Python Global Keyword Python Modules Python Package
Example of a recursive function
def factorial(x):
""
"This is a recursive function
to find the factorial of an integer ""
"
if x == 1:
return 1
else:
return (x * factorial(x - 1))
num = 3
print("The factorial of", num, "is", factorial(num))Output
The factorial of 3 is 6
Each function multiplies the number with the factorial of the number below it until it is equal to one. This recursive call can be explained in the following steps.
factorial(3) # 1 st call with 3 3 * factorial(2) # 2n d call with 2 3 * 2 * factorial(1) # 3 rd call with 1 3 * 2 * 1 # return from 3 rd call as number = 1 3 * 2 # return from 2n d call 6 # return from 1 st call
Last Updated : 13 Jun, 2022
Syntax:
def func(): < --
|
|
(recursive call) |
func() -- --Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Output:
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Factorial of number 6 = 720
720
The following fn() function is a recursive function because it has a call to itself:,A recursive function is a function that calls itself until it doesn’t.,And a recursive function always has a condition that stops calling itself.,The following defines a recursive count_down() function and calls it by passing the number 3:
The following fn() function is a recursive function because it has a call to itself:
.wp - block - code {
border: 0;
padding: 0;
}
.wp - block - code > div {
overflow: auto;
}
.shcb - language {
border: 0;
clip: rect(1 px, 1 px, 1 px, 1 px); -
webkit - clip - path: inset(50 % );
clip - path: inset(50 % );
height: 1 px;
margin: -1 px;
overflow: hidden;
padding: 0;
position: absolute;
width: 1 px;
word - wrap: normal;
word - break: normal;
}
.hljs {
box - sizing: border - box;
}
.hljs.shcb - code - table {
display: table;
width: 100 % ;
}
.hljs.shcb - code - table > .shcb - loc {
color: inherit;
display: table - row;
width: 100 % ;
}
.hljs.shcb - code - table.shcb - loc > span {
display: table - cell;
}
.wp - block - code code.hljs: not(.shcb - wrap - lines) {
white - space: pre;
}
.wp - block - code code.hljs.shcb - wrap - lines {
white - space: pre - wrap;
}
.hljs.shcb - line - numbers {
border - spacing: 0;
counter - reset: line;
}
.hljs.shcb - line - numbers > .shcb - loc {
counter - increment: line;
}
.hljs.shcb - line - numbers.shcb - loc > span {
padding - left: 0.75 em;
}
.hljs.shcb - line - numbers.shcb - loc::before {
border - right: 1 px solid #ddd;
content: counter(line);
display: table - cell;
padding: 0 0.75 em;
text - align: right; -
webkit - user - select: none; -
moz - user - select: none; -
ms - user - select: none;
user - select: none;
white - space: nowrap;
width: 1 % ;
}
def fn():
#...
fn()
#...
Code language: Python(python)Also, a recursive function needs to have a condition to stop calling itself. So you need to add an if statement like this:
def fn():
#...
if condition:
# stop calling itself
else:
fn()
#...
Code language: Python(python)For example, if you call the function that counts down from 3, it’ll show the following output:
3
2
1 Code language: Python(python)If you call the count_down() function now:
count_down(3) Code language: Python(python)The following defines a recursive count_down() function and calls it by passing the number 3:
def count_down(start):
""
" Count down from a number "
""
print(start)
count_down(start - 1)
count_down(3) Code language: Python(python)Syntax:
def rec_func_name():
if (condition) # base
case
simple statement without recursion
else # general
case
statement calling rec_func_name()def rec_func_name():
if (condition) # base
case
simple statement without recursion
else # general
case
statement calling rec_func_name()def rec_func_name():
if (condition) # base
case
simple statement without recursion
else # general
case
statement calling rec_func_name()Suppose you want to find the sum of n natural numbers. We would write the following code to get the answer.
def sum(n):
if n <= 1: # base
case
return n
else: # general or recursive
case
ans = sum(n - 1)
return n + ans
print(sum(6))def sum(n):
if n <= 1: # base
case
return n
else: # general or recursive
case
ans = sum(n - 1)
return n + ans
print(sum(6))Output:
21
def sum(n):
if n <= 1: # base
case
return n
else: # general or recursive
case
ans = sum(n - 1)
return n + ans
print(sum(6))21
Similarly, 3, 2, and 1 are printed in the following invocations. In the last call, the value of n becomes 0, and thus the base case is satisfied, causing recursion to terminate.
def dispn(n):
if n == 0:
return # Base
case
print(n)
dispn(n - 1) # Tail Recursive Call
dispn(5)def dispn(n):
if n == 0:
return # Base
case
print(n)
dispn(n - 1) # Tail Recursive Call
dispn(5)Output:
5 4 3 2 1
Thus, the print statement of disp(1) occurs before. So, the values are printed in ascending order.
def dispn(n):
if n == 0:
return # Base
case
dispn(n - 1) # Not a Tail Recursive Call
print(n)
dispn(5)def dispn(n):
if n == 0:
return # Base
case
dispn(n - 1) # Not a Tail Recursive Call
print(n)
dispn(5)This one is kind of fun. Here is the recursive function to reverse a string, and some very interesting strings that produce unexpected results when reversed!,The Fibonacci sequence happens everywhere in the world and in all of nature. The sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on is the Fibonacci sequence. Each successive number is found by adding up the two numbers before it. Here is how we compute the Fibonacci sequence in Python using a recursive function. It uses this process.,Factorial is the process of multiplying all the integers less than or equal to a given number. So, 5! is equivalent to 5*4*3*2*1 which is 120. We can use a recursive function to do this work for us. It will take just one argument, the number we want to apply a factorial to. For the breaking condition, if the given argument has reached zero we return the value of one. Otherwise, we return the number times factorial and decrement the number value. ,The output above shows the number of steps involved when there are only two rings. We can run the program again while using three rings, and you’ll see that the number of steps to solve the tower of Hanoi grows. Additionally, you can check out each step of the process in the visualizations.
Here we have a function named backwardsby2, which prints numbers in reverse order using steps of 2 starting with an initial number. The breaking condition is if the number is less than or equal to zero. In that case, we simply print Zero! If that condition is not met, the function calls itself using the current number – 2. We also initialize a list and add a smiley emoji equal to the current number. That way, as the counting backward happens, a corresponding number of emoji smiles will appear for each iteration. I think you’ll agree, this is an important feature of this recursion example.
def backwardsby2(num):
if num <= 0:
print('Zero!')
return
else:
emojismiles = []
for i in range(0, num):
emojismiles += '😃'
print(num, ' '.join(emojismiles))
backwardsby2(num - 2)
backwardsby2(9)9😃😃😃😃😃😃😃😃😃 7😃😃😃😃😃😃😃 5😃😃😃😃😃 3😃😃😃 1😃 Zero!
The Tower Of Hanoi is an ancient puzzle said to have originated in India or Vietnam. It involves moving various sized rings or disks around on three poles. The goal in this puzzle is to move all of the rings on one pole to another while keeping the order of the rings intact. You must follow the rules of the puzzle however, and this is that only one right can be moved at a time, and no ring may be placed on top of a smaller sized ring. This puzzle can be solved using recursion in Python, so let’s see that in action!
def towerOfHanoi(numrings, from_pole, to_pole, aux_pole):
if numrings == 1:
print('Move ring 1 from', from_pole, 'pole to', to_pole, 'pole')
return
towerOfHanoi(numrings - 1, from_pole, aux_pole, to_pole)
print('Move ring', numrings, 'from', from_pole, 'pole to', to_pole, 'pole')
towerOfHanoi(numrings - 1, aux_pole, to_pole, from_pole)
numrings = 2
towerOfHanoi(numrings, 'Left', 'Right', 'Middle')numrings = 3
towerOfHanoi(numrings, 'Left', 'Right', 'Middle')
Move ring 1 from Left pole to Right pole
Move ring 2 from Left pole to Middle pole
Move ring 1 from Right pole to Middle pole
Move ring 3 from Left pole to Right pole
Move ring 1 from Middle pole to Left pole
Move ring 2 from Middle pole to Right pole
Move ring 1 from Left pole to Right poleWe can use recursion to create a function that calculates the value of a number multiplied by itself a certain number of times. Of course, you have seen this many times. It is a common operation in Math to set a number to the power of a number. For instance, two to the fourth power is 16, two the fifth power is 32, and so on. We want to multiply an argument a given number of times. That means we need two arguments, one for the number itself, and one for the power it will be set to. The breaking condition is if the topwr variable is zero. This means we have completed all of the multiplications needed. It is the fact that this function recursively calls itself which provides a looping behavior.
def power(num, topwr):
if topwr == 0:
return 1
else:
return num * power(num, topwr - 1)
print('{} to the power of {} is {}'.format(4, 7, power(4, 7)))
print('{} to the power of {} is {}'.format(2, 8, power(2, 8)))By Bernd Klein. Last modified: 01 Feb 2022., 17 Oct 2022 to 21 Oct 2022
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)def factorial(n):
print("factorial has been called with n = " + str(n))
if n == 1:
return 1
else:
res = n * factorial(n - 1)
print("intermediate result for ", n, " * factorial(", n - 1, "): ", res)
return res
print(factorial(5))factorial has been called with n = 5
factorial has been called with n = 4
factorial has been called with n = 3
factorial has been called with n = 2
factorial has been called with n = 1
intermediate result
for 2 * factorial(1): 2
intermediate result
for 3 * factorial(2): 6
intermediate result
for 4 * factorial(3): 24
intermediate result
for 5 * factorial(4): 120
120def iterative_factorial(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
for i in range(5):
print(i, iterative_factorial(i))0 1 1 1 2 2 3 6 4 24
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n - 1) + fib(n - 2)