Recursive Algorithms
In general, programmers use two approaches to writing
repetitive algorithms. One approach uses loops; the
other uses recursion. Recursion is a repetitive process in
which a function calls itself.
Topics discussed in this section:
Fibonacci Numbers
• Iterative Algorithm
• Recursive Algorithm
Towers Of Hanoi
• Recursive Algorithm
• C++ Program Shahzad Akbar, Dept. of Computer Science, BZU, Multan 1
Fibonacci Numbers
The fibonacci series is defined as follows:
Iterative Algorithm
int Fib(int n)
0 if n=0
{
Fib(n) = 1 if n=1
a = 0;
Fib(n-1)+Fib(n-2) Otherwise
b = 1;
If(n=0 or n=1)
The series is 0 1 1 2 3 5 8 13 21 ...
return n;
n 0 1 2 3 4 5 6 7 8 ….. for (i = 2; i <= n; i++)
Fib(n) 0 1 1 2 3 5 8 13 21 …… {
c = a + b;
Iterative approach a = b;
• It is a repetition process until the specified b = c;
condition fails. }
• Loops are used in this approach such as for, return b;
while etc. }
• Iterative code may be longer but it is faster
than recursive
• It consumes less memory as compared to
Shahzad Akbar, Dept. of Computer Science, BZU, Multan 2
recursive approach.
Recursive Approach Recursive Algorithm
• Function calls itself until the int Fib(n)
base condition is met. {
• It is slower than iteration if (n=0 or n=1) //base condition
• It uses more memory than return n ;
iteration. else
• It makes code smaller and clean. return Fib(n - 1) + Fib(n - 2);
}
Fibonacci Recursive Calls
Fibonacci series is 0 1 1 2 3 5 8Shahzad
13 21 ...Dept. of Computer Science, BZU, Multan
Akbar, 3
Note: Recursive algorithms are mostly used
to solve complicated problems, for example,
Tower of Hannoi algorithm is made easy by
recursion as compared to iteration.
Shahzad Akbar, Dept. of Computer Science, BZU, Multan 4
Towers of Hanoi
Towers of Hanoi” is commonly used as an example of a problem with a
simple recursive solution.
There are three pegs.
The first (source) peg holds some number of discs.
You want to move all discs to the last (destination) peg.
You can only move one disc at a time.
You can never put a larger disc on top of a smaller disc.
You have one auxiliary peg you can use.
Shahzad Akbar, Dept. of Computer Science, BZU, Multan 5
Solution to Towers of Hanoi
Shahzad Akbar, Dept. of Computer Science, BZU, Multan 6
Recursive Algorithm of Tower of Hanoi
Recursive Calls
Hanoi(n, source, aux, destination)
{
if (n == 1) /* base case */
Move(source, destination);
else
{ /* recursion */
Hanoi(n-1,source,destination,aux);
Move(source, destination);
Hanoi(n-1,aux,source,destination);
}
}
Shahzad Akbar, Dept. of Computer Science, BZU, Multan 7
C++ Program of Tower of Hanoi
#include <iostream.h>
#include <conio.h>
void Hanoi(int n, char source, char aux, char destination); Output of Program for 3 discs
void main(void) Move disc 1 A to C
{ Move disc 2 A to B
Move disc 1 C to B
int discs; Move disc 3 A to C
cout << "Enter the number of discs: " << endl; Move disc 1 B to A
cin >> discs; Move disc 2 B to C
Hanoi(discs, 'A', 'B', 'C'); Move disc 1 A to C
getche();
}
void Hanoi(int n, char source, char aux, char destination)
{
if(n == 1)
cout << "Move disc " << n << " from " << source << " to " << destination << endl;
else
{
Hanoi(m-1, source, destination, aux);
cout << "Move disc " << n << " from " << source << " to " << destination << endl;
Hanoi(m-1,aux, source, destination);
} Shahzad Akbar, Dept. of Computer Science, BZU, Multan 8
}
Questions ?
Shahzad Akbar, Dept. of Computer Science, BZU, Multan 9
