Recursion is the process of a function calling itself from within its own code. You can think of it as another way to accomplish a looping construct. The recursion pattern appears in many scenarios in the real world, and we’ll cover some examples of recursion in Python here. A recursive function just keeps calling itself until it has completed the problem at hand. That brings up a good point, and that is to make sure that your recursive function actually terminates and returns at some point. Otherwise, the recursive function will run forever, exhaust your memory, and crash your computer. Having a step where the function actually finishes is known as a breaking condition. Each time a recursive function is called, the values of the arguments from the previous call are stored on the call stack.
Recursion Example 1: Counting backward by 2
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!
Recursion Example 2: Tower of Hanoi
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')
Move ring 1 from Left pole to Middle pole Move ring 2 from Left pole to Right pole Move ring 1 from Middle pole to Right pole
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.
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 pole
Tower of Hanoi beginning state
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 pole
Recursion Example 3: Set a number to a power
We 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)))
4 to the power of 7 is 16384 2 to the power of 8 is 256
Recursion Example 4: Factorial function
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.
def factorial(num):
if (num == 0):
return 1
else:
return num * factorial(num - 1)
print('{}! is {}'.format(4, factorial(4)))
print('{}! is {}'.format(2, factorial(2)))
4! is 24 2! is 2
Recursion Example 5: Fibonacci Sequence
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.
- If the number is 0, then the answer is 0.
- If the number is 1, then the answer is 1.
- Otherwise, the answer is the sum of the previous two Fibonacci numbers.
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
number = 14
print('Fibonacci sequence:')
for i in range(number):
print(fibonacci(i))
Fibonacci sequence: 0 1 1 2 3 5 8 13 21 34 55 89 144 233
Recursion Example 6: Sum of numbers from 1 to n
We can use recursion to find out the sum of numbers from 1 to n like 1 + 2 + 3 + 4 +, etc.
def sumnums(n):
if n == 1:
return 1
return n + sumnums(n - 1)
print(sumnums(3))
print(sumnums(6))
print(sumnums(9))
6 21 45
Recursion Example 7: Reverse a string
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!
def reverse(string):
if len(string) == 0:
return string
else:
return reverse(string[1:]) + string[0]
reverseme = 'Desserts'
print(reverse(reverseme))
reverseme = 'Knits'
print(reverse(reverseme))
reverseme = 'Regal'
print(reverse(reverseme))
reverseme = 'Pupils'
print(reverse(reverseme))
reverseme = 'Smart'
print(reverse(reverseme))
reverseme = 'Pals'
print(reverse(reverseme))
reverseme = 'Straw'
print(reverse(reverseme))
reverseme = 'Time'
print(reverse(reverseme))
reverseme = 'Star'
print(reverse(reverseme))stresseD stinK lageR slipuP tramS slaP wartS emiT ratS
Learn More About Recursion
- Recursion vs Loops in Python (hackernoon)
- How to understand recursive Python functions (stackabuse)
- Python recursive functions (thepythonguru)
- Technical Terms Recursive Function (techterms)
- Recursion examples (pythonspot)
- Learn Python Recursion Function (data-flair)
- Python Recursion Fibonacci (journaldev)
- Non-Programmer’s Tutorial for Python Recursion (wikibooks)
Python Recursion Examples Summary
Recursive functions call themselves either directly or indirectly resulting in a loop. This looping continues until a breaking condition is met. They may be used to traverse arbitrarily shaped structures, or for iteration in general. Python supports recursion, though it is not necessarily the simplest or most efficient approach in many situations. In this tutorial, we saw several examples of recursion in Python. Put the snippets in your IDE and test them out while changing the supplied arguments to the functions. This will help to better understand how they work. There are some drawbacks to recursive functions to be aware of. Recursive functions can be inefficient as they take up a lot of memory and time. In addition to that, sometimes the logic behind recursion is hard to follow making debugging problems difficult.
