30. Recursion

Recursion is a process by which a function calls itself repeatedly, until some specified condition has been satisfied. The process is used for repetitive computations in which each action is stated in terms of a previous result. Many iterative problems can be written in this form.

If you want to solve a problem recursively, two conditions must be satisfied. First, the problem must be written in a recursive form, and second one is , the problem statement must include a stopping condition. Suppose, for example, we wish to calculate the facttorial of a positive interger quantity. We would normally express this problem as n! = 1 * 2 * 3 * 4 *........... * n, where n is the specified positive integer. However, we can also express his problem in another way, by writting n! = n * (n-1)! This is a recursive statement of the problem, in which the desired action is expressed in terms of a previous result. Also, er know that 1!=1 by definition. This last expression provides a stopping condition for the recurion.

Example:
Look at this code :
unsigned int factorial(unsigned int a)
{
   if (a == 1)
   return 1;
   else
    {
      a *= factorial(a-1);
      return a;
   }
}

let a =4. Now when a=4 the if condition is false
so 4*=factorial(3);
but factorial( ) is a function so it call again. And again check the if condition where a=3 because the function call when a=3. But if condition is not true
so 3*=factoral(2); again call the function factoral where a=2. And again it check if conditon but it not true.
so 2* = factoral (1);  Now call the factoral and check the if conditon and if is true so it return 1. Now this is a importent point that every time when call the function factorial (), the return a ; is not work. Now it work. At last when the function call at the value of 1, the function return 1. so function (1)=1. Now put the value of facturl(1) in the point [a*=factorial(1)] and we get 2*1=2. the output is look like this:

let a=4
4 != 1 so the if portion is skipped for now.

4*=factorial(3)

3 != 1

3*=factoral(2)

2 != 1

2*=factoral(1)

1==1 so 1 is returned

2*1=2 so 2 is returned

2*3=6 so 6 is returned

6*4=24 so 24 is returned

The function doesn't get to the 'return a' until the factoral(a-1) returns a number which doesn't happen until a==1.

Recursive functions should be avoided at all costs because they get very unweildy very quickly. Large numbers would consume a lot of memory to do something as simple as a factorial.

post by arnob.