Recursion:
The process in which a function calls itself directly or indirectly is called recursion
and the corresponding function is called as recursive function.
Using recursive algorithm, certain problems can be solved quite easily.
Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder
Tree Traversals, DFS of Graph, etc.
Recursive functions are very useful to solve many mathematical problems, such as
calculating the factorial of a number, generating Fibonacci series, etc.
OR
A recursive function is defined as a function that calls itself to solve a smaller version
of its task until a final call is made which does not require a call to itself.
Since a recursive function repeatedly calls itself, it makes use of the system stack to
temporarily store the return address and local variables of the calling function.
Every recursive solution has two major cases. They are:
o Base case, in which the problem is simple enough to be solved directly without
making any further calls to the same function.
o Recursive case, in which first the problem at hand is divided into simpler sub-
parts. Second the function calls itself but with sub-parts of the problem obtained
in the first step. Third, the result is obtained by combining the solutions of
simpler sub-parts.
Example:
To understand recursive functions, let us take an example of calculating factorial of a
number.
To calculate n!, we multiply the number with factorial of the number that is 1 less than
that number.
In other words, n! = n * (n–1)!
Types Of Recursion:
Recursion is a technique that breaks a problem into one or more sub-problems that are
similar to the original problem.
Any recursive function can be characterized based on:
o whether the function calls itself directly or indirectly(direct or indirect
recursion),
o whether any operation is pending at each recursive call (tail recursive or not),
and
o the structure of the calling pattern (linear or tree-recursive).
1. Direct Recursion
2. Indirect Recursion
3. Tail Recursion
4. Head Recursion
5. Linear Recursion and
6. Tree Recursion
1. Direct Recursion:
a. function is said to be directly recursive if it explicitly calls itself.
b. For example, consider the code shown in Fig. 7.28. Here, the function
c. Func() calls itself for all positive values of n, so it is said to be a directly
recursive function.
2. Indirect Recursion:
a. A function is said to be indirectly recursive if it contains a call to another
function which ultimately calls it.
b. Look at the functions given below. These two functions are indirectly
recursive as they both call each other.
3. Tail Recursion:
a. If a recursive function calling itself and that recursive call is the last
statement in the function then it’s known as Tail Recursion.
b. After that call the recursive function performs nothing.
c. The function has to process or perform any operation at the time of
calling and it does nothing at returning time.
4. Head Recursion:
a. If a recursive function calling itself and that recursive call is the first
statement in the function then it’s known as Head Recursion.
b. There’s no statement, no operation before the call.
c. The function doesn’t have to process or perform any operation at the time
of calling and all operations are done at returning time.
5. Linear Recursion and Tree Recursion:
a. To understand Tree Recursion let’s first understand Linear Recursion.
b. If a recursive function calling itself for one time then it’s known
as Linear Recursion.
c. Otherwise if a recursive function calling itself for more than one time
then it’s known as Tree Recursion.
Tower of Hanoi:
The tower of Hanoi is one of the main applications of recursion. It says, ‘if you can
solve n–1 cases, then you can easily solve the nth case’.
Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and
more than one rings is as depicted –
These rings are of different sizes and stacked upon in an ascending order, i.e. the
smaller one sits over the larger one.
There are other variations of the puzzle where the number of disks increase, but the
tower count remains the same.
TOH Rules:
The mission is to move all the disks to some another tower without violating the
sequence of arrangement.
A few rules to be followed for Tower of Hanoi are −
– Only one disk can be moved among the towers at any given time.
– Only the "top" disk can be removed.
– No large disk can sit over a small disk.
Solution for Single Disc:
Solution for Two Disc:
Solution for 3 Disc:
Solution for N Discs:
Note:
• Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps.
• The presentation shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps.