|

# Python Recursion Examples 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

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```