Python Recursion Function

Python Recursion Function

If we call a function from within the same function, then it is called Recursion Function.

Examples

1. Find factorial using recursion

Finding factorial of a given number is a classic example for Recursion Function.

In the following program, we read a number from user, and find its factorial using the recursion function. factorial() is the recursion function. Please observe that inside factorial() function, we are calling the same factorial() function, but of course with modified argument.

Python Program

def factorial(n):
    result = 1
    if n > 0:
        if n > 1:
            return n * factorial(n - 1)
    return result

n = 5
result = factorial(n)
print(f'{n}! = {result}')

Output

5! = 120

2. Tower of Hanoi Program using Recursion

In this example, we will solve the Tower of Hanoi problem using recursion technique.

We define a function tower_of_hanoi(). This function has following four parameters.

1. n - the number of disks.
2. from_rod - The rod which has all the disks at the start.
3. to_rod - The rod to which all the disks has to be moved.
4. aux_rod - The auxiliary rod which can be used to place the disks temporarily.

For a detailed explanation about Tower of Hanoi problem, and its solution, please refer the tutorial, Tower of Hanoi Program.

Python Program

def tower_of_hanoi(n, from_rod, to_rod, aux_rod):
    if n == 1:
        print("Move disk 1 from rod", from_rod, "to rod", to_rod)
        return
    tower_of_hanoi(n-1, from_rod, aux_rod, to_rod)
    print("Move disk", n, "from rod", from_rod, "to rod", to_rod)
    tower_of_hanoi(n-1, aux_rod, to_rod, from_rod)
 
# Number of disks
n = 4
tower_of_hanoi(n, 'A', 'C', 'B')

Output

Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C

Summary

In this tutorial, we discussed what a Recursion Function is, and how to write a recursion function in a Python program, with examples.