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;
}
}