Recursion

Recursion:

Suppose P is a procedure containing either call statement to itself or call statement to a second procedure that may eventually result in call statement back to the original procedure P then P is called as recursive procedure.

A recursive procedure must have the following two properties:

1. There must be a certain criteria, call base criteria, for which the procedure does not call to itself.
2. Each time the procedure does call itself, it must be closer to base criteria.

Similarly, a function is said to be a recursively define if function definition refers to itself.

 In order for the definition not to be circular, it has the following properties

1. There must be a certain augment, called base value.  For which function does not refers to itself.
2. Each time the function does refer to itself, the argument of the function must be closer to a base value.

Factorial function:

The product of the positive integer from 1 to n, is called ‘n factorial’ and usually denoted by n!

                                                n!=1*2*3*…(n-2)*(n-1)*n

 It is also convenient do define 0!=1, so that the function is defined for all the non-negative integers.

Thus we have

         0!=1                         1!=1                        2!=2*1=2                              3!=3*2*1=6

4!=4*3*2*1=24                                              5!=5*4*3*2*1=120

And so on. Observe that

            5!=5*4! =5*24=120              and                6!=6*5!=6*120=720

That is true for every positive integer n; that is

                                                 n!=n*(n-1)!

 Definition: (Factorial Function)

      a)    If n=0, then n!=1

b)    If n>0, then n!=n*(n-1)!

Procedure: FACTORIAL (Fact, N)

This procedure calculates N! and return the value in the variable FACT.

 1.    If N=0, then: Set FACT:=1 and Return.

 2. Set FACT:=1 [Initialize FACT for loop.]

 3. Repeat for I =1 to N

Set FACT*=FACT*I

[End of loop]

4.   4. Return.

Procedure: FACTORIAL (Fact, N)

This procedure calculates N! and return the value in the variable FACT.

1.    If N=0, then: Set FACT:=1 and Return.

2.  Set FACT*=N*FACT

3.  Call FACTORIAL(FACT, N-1)

4.  Return.

Fibonacci sequence:

Fibonacci sequence usually denoted by(F0,F1,F2) as follows:

0,         1,         1,         2,         3,         5,         8,         13,       21,       34,       55..

That is, F=0 and F1=1 and each succeeding term is a sum of two preceding term:

For example, the next two term of a sequence is

34+55=89                              55+89=144

 

Def: (Fibonacci sequence)

a)    If N=0 or N=1, then Fn=n

b)    If n>1, then Fn=Fn-2+Fn-1

Procedure: FIBONACCI (FIB, N)

This procedure calculates Fn and return the value of in the first parameter FIB.

1. If  N=0 or N=1 , then: Set FIB:=N, and Return

2. Call FIBONACCI (FIBA, N-2)

3. Call FIBONACCI (FIBB, N-1)

4. Set FIB:=FIBA+FIBB.

5. Return.