Transcript Recursion
The process of solving a problem by reducing it
smaller versions of itself is called recursion
Recursion is a powerful way to solve some certain
problems for which the solution otherwise will be
very complicated
Example: Factorail , Fibonacci numbers and Towers
of Hanoi
Factorial
n!=n*(n-1)! if
n>0
and
0!=1
Recursive definition: A definition in which something is defined
in terms of a smaller version of itself
int fact (int num)
{
if(num = = 0)
return 1;
else
return num * fact(num-1);
}
Direct and Indirect
Recursion
A function is directly recursive if it calls itself
A function that calls another function and eventually
results in original function call is said to be
indirectly recursive
if function A calls B and B calls A, then function A is
recursive
if function A calls B and B calls C and C calls D and D
calls A, then A function is recursive
Infinite Recursion
If every recursive call results in another recursive
call, then the recursive function (algorithm) is said to
have infinite recursion
As a theory infinite recursion executes forever
But , because the memory is finite the recursive
function will execute till the system runs out of
memory and results in abnormal termination of
program
How to design
Recursive program
understand the problem requirements
determine the limiting conditions
identify the base case and provide a direct solution
to each base case
identify the general cases and provide a solution to
each general case in terms of smaller versions of
itself
Largest element in array
Pseudo code:
Base case:
the size of the arr is 1
the only element in the arr is the largest
General case: The size of the arr is greater then 1
to find the largest element in arr[a]…arr[b]
- find the largest element in arr[a+1]…arr[b]
and call it max
- compare the elements arr[a] and max
if (arr[a]>=max )
the largest element in arr[a]…arr[b] is arr[a]
otherwise
the largest element in arr[a]…arr[b] is max
int largest(const int arr[], int lowerIndex, int upperIndex)
{
int max;
if (lowerIndex == upperIndex)
return arr[lowerIndex];
else
{
max=largest(arr, lowerIndex+1, upperIndex);
if (arr[lowerIndex]>= max)
return arr[lowerIndex];
else
return max;
}
}
Fibonacci numbers
Fibonacci number is the sum of the first two
numbers of Fibonacci.
Fn= Fn-1 + Fn-2
In mathematics, the Fibonacci numbers or Fibonacci
series or Fibonacci sequence are the numbers in the
following integer sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
F0
0
F1
1
F2
1
F
F
F
F
F
F
F
F
F
F
F
F
F
F
3
4
5
6
7
8
9
10
11
12
13
14
15
16
8
1
3
2
1
3
4
5
5
8
9
2
3
3
3
7
7
6
1
0
9
8
7
2
3
5
…;1
4
4
F17
F18
F19
F20
1597
2584
4181
6765
Applications
computer algorithms:
Fibonacci search technique
Fibonacci heap data structure
Fibonacci cubes used for interconnecting parallel and
distributed systems
biological settings:
branching in trees
phyllotaxis (the arrangement of leaves on a stem)
fruit sprouts of a pineapple
flowering of artichoke
an uncurling fern
arrangement of a pine cone
Applications
Function of Fibonacci
numbers (C++)
int FibNum(int first, int second, int nth)
{
if (nth == 1)
return first;
else if (nth == 2)
return second;
else
return FibNum(first, second, nth-1) +
FibNum(first, second, nth-2);
}
Towers of Hanoi
(recursive)
FUNCTION MoveTower(disk, source, dest, spare):
IF disk == 0, THEN:
move disk from source to dest
ELSE: MoveTower(disk - 1, source, spare, dest)
// Step1 above
move disk from source to dest
// Step 2 above
MoveTower(disk - 1, spare, dest, source)
// Step 3 above
END IF
Diagram view how function
ToH works
main function
#include <iostream>
using namespace std;
void moveDiscs(int, int, int, int, int);
void main()
{
int count = 0;
int NUM_DISCS = 3;
// Number of discs to move
const int FROM_PEG = 1;
// Initial "from" peg
const int TO_PEG = 3;
// Initial "to" peg
const int TEMP_PEG = 2;
// Initial "temp" peg
moveDiscs(NUM_DISCS, FROM_PEG, TO_PEG, TEMP_PEG, count);
cout << "All the pegs are moved!\n";
system("PAUSE");
}
moveDiscs Function
if (fromPeg == 1 &&
void moveDiscs(int num, int
fromPeg, int toPeg, int
tempPeg, int count)
{
if (num > 0)
{
moveDiscs(num - 1,
fromPeg, tempPeg, toPeg,
count);
cout << "Move a disc from
peg " <<fromPeg
<< " to peg " <<
toPeg <<endl;
count++;
toPeg == 3)
{
if (num == 1)
{
if(count == 3)
cout<<"
*"<<endl<<" *"<<endl<<"
*"<<endl;
else
cout<<
"*"<<endl<<"* *"<<endl;
}
else
cout << " *"<<endl
<<" * *"<<endl;
}
if (fromPeg==1 && toPeg==2)
cout << "* * *"<<endl;
if (fromPeg ==3 &&
toPeg==2)
cout << " *"<<endl <<"*
*"<<endl;
if (fromPeg==2 && toPeg==1)
cout << "* * *"<<endl;
if (fromPeg==2 && toPeg==3)
cout << " *"<< endl <<"*
*"<<endl;
moveDiscs(num-1, tempPeg,
toPeg, fromPeg, count);
}
}
Output of the program ToH
Another function of ToH
void moveDisks(int count, int peg1, int peg3, int peg2)
{
if (count>0)
{
moveDisks(count-1, peg1, peg2, peg3);
cout<<"Move disk"<<count
<< " from " << peg1
<< " to " << peg3
<< " . " << endl;
moveDisks(count-1, peg2, peg3, peg1);
}
}
Binary to Decimal
To convert binary number to decimal
find the weight of each bit from right to left
weight of rightmost bit is 0
multiply the bit by 2 to the power of it’s weight and
add all of the numbers
Binary to Decimal
Recursive solution
void binToDec(int binary, int& decimal, int& weight)
{
int bit;
if (binary>0)
{
bit=binary % 10;
decimal=decimal+bit*static_cast<int>(pow(2.0,weight));
binary=binary/10;
weight++;
binToDec(binary, decimal, weight);
}
}
Decimal to Binary
To convert decimal to binary
divide decimal number by 2 till dividend will be less
then 2
the first remainder of division is the left leftmost
element of binary number and the last remainder is
rightmost element of binary number
write the remainders in their positions
Decimal to Binary
Recursive solution
void decToBin(int num, int base)
{
if (num > 0)
{
decToBin(num/base, base);
cout << num % base;
}
}