RECURSION

RECURSION

When a called function in turn calls another function a processng of ‘chaining’ occurs. Recursion is a special case of this process, where a function calls itself. A very simple example of recursion is the evaluation of

              factorials of a given number.

  The factorial of a number n is expressed as a series of repetitive multiplications as shown below:

 factorial of n = n(n-1)(n-2) ....................1

A function to evaluate factorial of n is as follows:

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

Let us see how the recursion works. Assume n = 3. Since the value of n is not
1, the statement
fact = n * factorial(n-1);
ill be executed with n = 3. That is,
fact = 3 * factorial(2);
will be evaluated. The expression on the right-hand side includes a call to
factorial with n = 2. This call will return the following value:
2 * factorail(1)
Once again, factorial is called with n = 1. This time, the function returns 1.
The sequence of operations can be summarized as follows:
fact = 3 * factorial(2)
= 3 * 2 * factorial(1)
= 3 * 2 * 1
= 6

Recursion function can be effectively used to solve problems where the solution is expressed in terms of successively applying the same solution to subsets of the problem. When we write recursive functions, we must have an if statement somewhere to force the function to return without the recursive  call being executed.