Understanding Recursion: A Powerful Problem-Solving Technique

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 and n>0 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) else } return 1; 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: General case: and call it max the size of the arr is 1 the only element in the arr is the largest 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] - 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, F F F F F F F F F F F F F F F0 F1 F2 F17 F18 F19 F20 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ; 8 9 1 4 4 2 3 3 3 7 7 6 1 0 9 8 7 1 3 2 1 3 4 5 5 0 1 1 2 3 5 8 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; 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"); } // Number of discs to move

moveDiscs Function if (fromPeg == 1 && toPeg == 3) { if (num == 1) { if(count == 3) cout<<" *"<<endl<<" *"<<endl<<" *"<<endl; else cout<< "*"<<endl<<"* *"<<endl; } 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++;

else if (fromPeg==2 && toPeg==1) cout << "* * *"<<endl; if (fromPeg==2 && toPeg==3) cout << " *"<< endl <<"* *"<<endl; cout << " *"<<endl <<" * *"<<endl; } if (fromPeg==1 && toPeg==2) cout << "* * *"<<endl; if (fromPeg ==3 && toPeg==2) 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; } }