Recursion

Recursion is a powerful problem solving technique. It solves a problem by breaking it down into similar and simpler subproblems.

Some definitions:

Base Case: The case for which the solution can be stated non-recursively.
General Case: The case for which the solution is expressed in term of a smaller version of itself; also known as recursive case.
Recursive algorithm: A solution that is expressed in terms of (a) smaller instance of its self and/general case (b) a base case.
Infinite Recursion: The situation in which a function calls itself over and over endlessly. How can this happen?

The Best way to demonstrate recursion is by showing an example.

    //file:Expo.C 
    #include<iostream.h>

    int Power(int,int);

    int main()
    {
      int number;         //number that is being raised to power
      int exponent;	  //Power the number is being raised to
      
      cin >> number >> exponent;
      cout << Power(number,exponent);
      
      return 0;
    }

    int Power(int x,int n)
    {
      if (n == 1)    //Base Case
        return x;
      else
        return x* Power(x,n-1);  //General Case
    }

To visualize the code, consider number=2 and exponent=5