5 Python Recursion Exercises and Examples

In programming, recursion is a technique using a function or an algorithm that calls itself one or more times until a particular condition is met. 

A recursive function is a function that calls itself with a failure condition. It means that there will be one or more function calls within that function definition itself.

Let’s see how we can implement recursion using Python. In this article, I have provided a few examples of using recursion in Python. Check out these examples, and I hope they will help you get a clear idea about the concept of recursion in programming. Let’s dive right in.

Example 1: Finding the factorial of a number

If you are familiar with the concept of factorial in mathematics, this will be a simple example of recursion for you to start with. In mathematics, the equation for finding the factorial of a number is as follows:

n! = n * (n-1)!

Given below is a Python program that finds out the factorial of a number by calling a function recursively.

def fact(n):
  if(n==1):
    return n
  else:
    return n*(fact(n-1))


num = int(input("Enter a number: "))

if num<0:
  print("Negative numbers are not allowed.")
elif num==0:
  print("Factorial is: 1")
else:
  print("Factorial is: ",fact(num))

Example 2: Fibonacci Series

Fibonacci is a special kind of series in mathematics in which the current term is the sum of the previous two terms. For example, a Fibonacci series would look like this:

0, 1, 1, 2, 3, 5, 8, 13,…

In this series, the next number is found by adding the two numbers before that.

Given below is a Python code that finds out the Fibonacci series till a number n.

def fib(n):
  if n<=1:
    return n
  else:
    return fib(n-1) + fib(n-2)

count = int(input("Enter the limit: "))

if count<=0:
  print("Enter a number greater than 0")
else:
  for i in range(count):
    print(fib(i),end=" ")

Example 3: Finding the power of a number

The mathematical equation for finding the power of a number is as follows:

p(base, exp) = base * p(b, exp-1) 

For example, 2³ = p(2, 3) = 2 * p(2,2)

The Python code for finding the power of a number is given below:

def power(base,exp):
  if exp == 0:
    return 1
  if exp==1:
    return base
  else:
    return base*(power(base,exp-1))

b = int(input("Enter the base value: "))
e = int(input("Enter the exponent value: "))
print("The result is:", power(b,e))

Example 4: Combination

You might have heard about permutations and combinations in mathematics. In this example, let’s see how we can find out combinations using Python recursive functions.

Here is the equation for finding the combination:

nCr = n! / r! (n-r)!

Here, n is the total number of items and r is the number of combinations needed.

For example, consider taking combinations of 2 values from A, B, C, D.

⁴C₂ = 4! / 2! (4-2)! = 24/2(2) = 24/4 = 6

The Python code for implementing combinations is given below:

def fact(n):
  if(n==1):
    return n
  else:
    return n*(fact(n-1))

def combination(n,r):
  return fact(n)/(fact(r)*fact(n-r))

n = int(input("Enter n: "))
r = int(input("Enter r: "))
print(int(combination(n,r)))

Example 5: Tower of Hanoi

Tower of Hanoi is a mathematical problem where we have three rods and n disks. The goal of this puzzle is to move all the disks to another rod, obeying the following rules: 

• Move only one disk at a time
• You can’t place a larger disk over a smaller disk
• The disks are put in ascending order of their size at the start.

Generic algorithm (considering A as the starting tower, B as the ending tower, and C as the auxiliary tower):

• Move n-1 disks from A to C using B
• Move 1 disk from A to B
• Move n-1 disks from C to B using A

Given below is the Python code for solving the Tower of Hanoi problem.

def toh(n,start,end,aux):
  if(n==1):
    print("Move disk 1 from",start,"to",end)
    return
  toh(n-1,start,aux,end)
  print("Move disk",n,"from",start,"to",end)
  toh(n-1,aux,end,start)

n = int(input("Enter the number of disks: "))
toh(n,'A','B','C')