Recursion refers to the technique of defining a process in terms of its own. It is used to solve complex programming problems that are repetitive in nature.
The basic idea behind recursion is to break a problem into smaller versions of its own, and then, build a solution for the entire problem. This may sound similar to the divide and conquer technique.
However, the recursion technique is different from the divide and
conquer technique. Divide and conquer is a theoretical concept that may be implemented in a computer program with the help of recursion.
Recursion is implemented in a program by using a recursive procedure or function. A recursive procedure is a function that invokes on its own.
Consider a function f(n), which is the sum of the first n natural numbers. This function can be defined in different ways.
In mathematics, the function will be defined as:
f(n) = 1 + 2 + 3 + 4 + 5 +…+ n
However, the same function can be defined in a recursive manner as:
f(n) = f(n – 1) + n
Where n > 1 and f(1) = 1
In this case, the recursive definition of the f(n) function calls the same function, but its arguments are reduced by one. Recursion will end when n = 1. In that case, f(1) = 1.
To understand this concept, consider a factorial function. A factorial function is defined as:
n! = 1 × 2 × 3 × 4 × … × n
This same factorial function can be redefined in a recursive manner as n! = (n – 1)! × n where n > 1 and 0! = 1
This definition of n! is recursive because it refers to itself when it uses (n -1)!. The value of n! is explicitly given when n = 0 and the value of n! for
arbitrary n is defined in terms of the smaller value of n, which is closer to the base value, 0.
If you have to calculate 3! by using recursion, you first define 3! in terms of 2! as 3! = (3 × 2!) Now, you will define 2! in terms of 1! as 3! = (3 × (2 × 1!))
Now, you will define 1! in terms of 0! as:
3! = (3 × (2 × (1 × 0!)))
Now, 0! is defined as 1. Therefore, the expression becomes:
3! = (3 × (2 × (1 × 1)))
3! = (3 × (2 × 1))
3! = (3 × 2)
3! = 6
The recursive algorithm for determining the factorial of a number, n, can be written as:
1. If n = 0, then: // Terminatingcondition
2. Return (n × Factorial(n – 1)).
Please note that every recursive algorithm should have a terminating condition. Otherwise, the algorithm will keep on calling itself infinitely.
The main advantage of recursion is that it is useful in writing clear, short, and simple programs. One of the most common and interesting problems that can be solved by using recursion is the Tower of Hanoi problem.
Tower of Hanoi
Tower of Hanoi is a classical problem, which consists of ‘n’ different sized disks and three pins over which these disks can be mounted.
All the disks are placed on the first pin with the largest disk at the bottom, and the remaining disks are placed in decreasing order of their
size, as shown in the following figure.
The objective of the game is to move all disks from the first, pin to the third pin in the least number of moves by using the second pin as an intermediary.
To play this game, you need to follow the following rules:
1. Only one disk can be moved at a time.
2. A larger disk cannot be placed over a smaller one.
Let n be the number of discs. If n = 3, it will require seven moves to transfer all discs from pin one to pin three, as shown in the following table.
The moves given in the preceding table are illustrated in the following figure.