RECURSION
For drawings using Recursion click:     Drawings
A Recursive Method is a method that calls itself either directly or indirectly through another method.  A recursive method is called to solve a problem.  The method actually knows how to solve only the simplest case(s) or so called base case(s).  When it is called with the base case, it returns a result.  Otherwise the method calls itself until it reaches the base case.
Programs using Recursion can be made to do all sorts of things, right from calculating the factorial of a number, to playing complex games against human intelligence.  In normal procedural languages, one can go about defining functions and procedures, and 'calling' these from the 'parent' functions.  Some languages (such as C++ and Java) also provide the ability of a function to call itself.  This is called Recursion.
A good example of recursion is the determination of a Factorial.  Factorial is a mathematical term.  Factorial of a number, say n, is equal to the product of all integers from 1 to n. Factorial of n is denoted by n! = 1x2x3...x n.  E.g.: 10! = 1x2x3x4x5x6x7x8x9x10
The simplest program to calculate factorial of a number is a loop with a product variable. Instead, it is possible to give a recursive definition for Factorial as follows:

                         1) If n=1, then Factorial of n = 1
                         2) Otherwise, Factorial of n = product of n and Factorial of (n-1)

                         Check it out for yourself; it works. The following code fragment depicts Recursion at work.

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

Other examples of recursion are summation of numbers and the  Fibonacci series, named after  Leonardo Fibonacci

The important thing to remember when creating a recursive function is to give an 'end-condition'. We don't want the function to keep calling itself forever? Somehow, it should know when to stop. There are many ways of doing this. One of the simplest is by means of an 'if condition' statement, as above. In the above example, the recursion stops when n reaches 1. In each instance of the function, the value of n keeps decreasing. So it ultimately reaches 1 and ends. Of course, the above function will run infinitely if the initial value of n is less than 1. So the function is not perfect. The n==1 condition should be changed to n<=1.

Other examples include Mazes, the Towers of Hanoi,  Magic Squares  Tic-Tac-Toe (or Noughts and Crosses)
 

Recursion can also be used in drawings such as fractals, the Koch snowflake, and in the creation of a Sierpinski Gasket shown below.
The answer to the question, "How do you make a Sierpinski Gasket?" is a procedure which is recursively defined. 

Procedure for Making a Sierpinski Gasket

     Connect the midpoints of two equilateral triangles. 
     Cut out the triangle which results 
     Make Sierpinski Gaskets out of the three remaining triangles. 
Making Sierpinski Gaskets involves making Sierpinski Gaskets. Each time you do the procedure, you do the procedure some
more, but not in a repetitive way. (Otherwise we would be talking about repetition and not recursion!)

You don't make the second, third and fourth Sierpinski Gaskets after you make the first one. Making the next three is part of
making the first one. All the ones you make after that will be part of those three which are part of the first one.

Recursion vs. Iteration.  Some of the problems such as summation, factorials, and Fibonacci numbers can be solved easier by iteration.  Recursion has many negatives.  It repeatedly invokes the mechanism and, consequently the overhead, of method calls.  Each recursive call causes the variables another method to be created, requiring considerable memory space.  However some problems like the Towers of Hanoi and the Sierpinski gasket can only be solved by the recursion process.