Recent Post

Recursion

Recursion is a function which calls itself either directly or indirectly.
Factorial function:

                 int fact(int n)
                  {
                       if(n==0)return 1;
                        else return n*fact(n-1);
                  }

Fibonacci sequence:

               int fib(int n)
                {
                   if(n<2)return n;
                   else return fib (n-1) + fib(n-2);
  
                 }
(i) The number of function calls in fib(n)=2*fib(n+1)-1
(ii) The number of addition in fib(n) = fib(n+1)-1
(iii) In fib(n) after(n+1) function calls first addition will be performed.

Tower of Hanoi: (A : source, B : temporary, C : destination)
     TOH (A, B, C, n)
        {
             if (n-1) C.PUSH (POP(A));
              else
               {
                 TOH (A, B, C, n-1);
                  C.PUSH (POP (A));
                 TOH (B, C, A, n-1);
                } 
          }

(i) Number of function calls in TOH (n) = 2n-1 -1

(ii) Number of moves in TOH (n) = 2n-1




GCD of two number (iteration)
              f(a,b)
                 {
                    while (B not equal to 0)
                         {
                             t = b;
                              b = a mod b;
                               a = t;
                            }
                             return a;
                      }

GCD of two numbers (recursive function) 

                   f( a, b)
                      {
                           if (a=b)return a;
                            else if (a>b) return f(a-b , b);
                             else f( a , b-a);    // if  ( a<b)
                      }

Finding the second maximum of three (distinct) numbers:

      int trial ( int a , int b , int c )
           {
                 if (( a>= b) && (c<b) return b;
                 else if ( a>=b) return trial (a, c, b,);
                  else return trial ( b, a, c);
            }







No comments