>>Send ur suggestion to Mynotes Tab

Recursion

3.1 Introduction
3.2 Definition of Recursion and processes
3.3 Recursion in C
3.4 Example of recursion:- Factorial Function, Fibonacci
Series, Tower of Hanoi Problem
3.5 Simulating recursion
3.6 Backtracking
3.7 Recursive algorithms
3.8 Principles of recursion
3.9 Tail recursion
3.10 Removal of recursion

Recursion is a name given to a technique for defining a function in terms of itself. A function definition which defines it in terms of a simpler case of itself is called a recursive definition. A definition which defines an object in terms of a simpler case of itself is called a recursive definition.


In order for a function definition not to be circular, the function definition must have the following two properties:-

(i) there must be certain arguments, called base values, for which the function does not refer to itself.

(ii) Each time the function does refer to itself, the argument of the function must be closer to the base value.

Example- Recursive definition of Factorial Function:-


(i) if n=0, then n!=1
(ii) if n> 0, then, n!=n x (n-1)!




We see that this definition of n! is recursive, since it refers to itself when it uses ( n - 1 )!. In (i), the value of n! is explicitly given when n=0, thus 0 is the base value. In (ii), the value of n! for arbitrary n is defined in terms of a smaller value of n which is closer to the base value 0. Accordingly the definition of factorial function is not circular, in other words, the function is well-defined.


(1) 4!=4 x 3!

(2) 3!= 3 x 2!

(3) 2!= 2 x 1!

(4) 1!=1 x 0!

(5) 0!=1


Each case is reduced to a simpler case until we reach the case of 0! which is defined directly as 1. We, backtrack from line (5) to line (1) , returning the value completed in one line to evaluate the result of the previous line. This produces

(5) 0! = 1

(4) 1! =1 x 0! = 1 x 1 = 1


(3) 2! = 2 x 1! = 2 x 1 = 2


(2) 3! = 3 x 2! = 3 x 2 = 6


(1) 4! = 4 x 3! = 4 x 6 = 24


Let us convert this concept of factorial function into C-language function:-


int fact(int n)

{

If ( n == 0)

return 1;

Else

return n * fact(n-1);

}

The sequence of recursive calls when fact(4) is called is as follows:-






Now let us write C-program for finding the factorial of a given integer:-


#include<stdio.h>
int fact(int n)
{

if ( n == 0)

return 1;

else

return n * fact(n-1);

}


void main()


{

int x, f;

printf(“\n Enter a positive integer:”);

scanf(“%d”,&x);

f=fact(x);


printf(“\n The factorial of %d is %d”,x,f);

}


The output of this program is given below:-


Output



Enter a positive integer: 4


The factorial of 4 is 24


Recursive definition of Fibonacci series


(i) if n = 0 or n = 1, then fn=n

(ii) if n > 1, then fn=fn - 2 + fn - 1


This definition of Fibonacci series is recursive, since the definition refers to itself when it uses fn-2 and fn-1.In (i), the base values are 0 and 1 and in (ii), the value of fn is defined in terms of smaller values of n which are closer to the base values. Accordingly this function is not circular, i.e. well-defined.


Let us write C-function for the Fibonacci series:-

unsigned Fib(unsigned n)

{

if(n==0)
return 0;

else if ( n==1)

return 1;

else

return Fib( n-2) + Fib(n-1);

}



The sequence of recursive calls when fib(4) is calls is given below:-















Let us write the C-program for Fibonacci sequence


#include<stdio.h>

unsigned Fib(unsigned n)


{

if(n==0)

return 0;

else if ( n==1)

return 1;

else

return Fib( n-2) + Fib(n-1);

}

void main()

{


unsigned n,i;


printf(“\n How many Fibonacci numbers?”);

scanf(“%d”,&n);

printf”\n Fibonacii sequences are:”);

for ( i=0, i<=n, i++)

printf(”%u\t”,Fib(i));

}


The output of this program is as follows:-


Output



How many Fibonacci Numbers? 5


0 1 1 2 3 5






Tower of Hanoi Problem:


A tower of n disks is initially placed in decreasing size on one of the three pegs. The goal is to transfer the entire tower of disks from peg one to peg three suing an auxiliary peg two.


The rules of the game are as follows:-


(i) only one disk may be moved at a time, specifically, only the top disk on any peg may be moved to the any other peg.


(ii) At no time can a larger disk be placed on a smaller disk.


Suppose three pegs A, B, C are given, and suppose on peg A, there is on disk.


Then, to move top disk from A to C, denoted by A → C, we have only one move A → C.


Now, suppose one peg A, there are two disks.


Then,


move top disks from A → B.


move top disks from A → C.


move top disks from B → C.



Now, Suppose, there are three disks on peg A.


Then,


move top disks from A → C

move top disks from A → B

move top disks from C → B

move top disks from A → C

move top disks from B → A

move top disks from B → C

move top disks from A → C