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) = 2^n-1 -1

^{(ii) Number of moves in TOH (n) =} 2ⁿ-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);

            }