You cannot copy content of this page.

Oct 2,2012
Leave a comment
By admin

#include <stdio.h>

#include <conio.h>

int power(int x,int n)

{

if(n==0)

return 1;

else

return(x * power(x,n-1));

}

void main()

{

int x,n,res;

clrscr();

printf(“nEnter base?”);

scanf(“%d”,&x);

printf(“nEnter exponent?”);

scanf(“%d”,&n);

res=power(x,n);

printf(“Power of %d raised to %d is %d”,x,n,res);

getch();

}

#include <stdio.h>

#include <conio.h>

/*Recursive function to compute GCD*/

int GCD(int x,int y)

{

if(y==0)

return x;

else if(x<y)

return GCD(y,x);

else

return GCD(y,x%y);

}

void main()

{

int x,y,res;

clrscr();

printf(“nEnter first number?”);

scanf(“%d”,&x);

printf(“nEnter second number?”);

scanf(“%d”,&y);

res=GCD(x,y);

printf(“nGCD of %d and %d is %d”,x,y,res);

getch();

}

#include <stdio.h>

#include <conio.h>

void hanoi(int num_disks,char *src,char *tmp,char *trgt);

void main()

{

int disks;

char source[10],temp[10],target[10];

clrscr();

printf(“nEnter total number of disks?”);

scanf(“%d”,&disks);

printf(“nEnter source pillar?”);

scanf(“%s”,source);

printf(“nEnter intermediate pillar?”);

scanf(“%s”,temp);

printf(“nEnter target pillar?”);

scanf(“%s”,target);

hanoi(disks,source,temp,target);

getch();

}

void hanoi(int num_disks,char *src,char *tmp,char *trgt)

{

if(num_disks==1)

{printf(“nMove disk from %s to %s”,src,trgt);

}

else

{

hanoi(num_disks-1,src,trgt,tmp);

printf(“nMove disk from %s to %s”,src,trgt);

hanoi(num_disks-1,tmp,src,trgt);

}

}

**Output:**

Enter total number of disks?3

Enter source pillar?First

Enter intermediate pillar?Second

Enter target pillar?Third

Move disk from First to Third

Move disk from First to Second

Move disk from Third to Second

Move disk from First to Third

Move disk from Second to First

Move disk from Second to Third

Move disk from First to Third

#include <stdio.h>

#include <conio.h>

/*Recursive Definition*/

/*int factorial(int n)

{if(n==0)

return 1;

else

return(n*factorial(n-1));

}

*/

/*Non-Recursive Definition*/

int factorial(int n)

{int i,res=1;

for(i=n;i>=1;i–)

res=res*i;

return(res);

}

void main()

{

int num,res;

clrscr();

printf(“nEnter number to compute factorial?”);

scanf(“%d”,&num);

res=factorial(num);

printf(“nFactorial = %d”,res);

getch();

}

A function call is said to be recursive, if we invoke a function from within the same function. The phenomenon being referred to as recursion. A termination condition must be specified with each recursive call to avoid infinite execution of that function. Recursion is basically required whenever a function has to operate upon different set of values to obtain the result.

The recursive calls must store the intermediate results of arguments of arguments and local variables. Recursive calls cannot store these values in the memory allocated to variables during compile time, hence dynamic memory management issues are involved in recursion. Thus, the arguments must be stored along with the return address to evaluate the result, since most recently saved variables are restored first. Thus activation stacks are created which support LIFO (Last In First Out) order for the purpose of evaluating result in recursion.

Thus recursion may also be used in programs that must operate in Last In First Out order. Recursive programs may also be written using non-recursive approach to programming either with the use of stack or by using GOTO to transfer the control to any specific part of the program, wherever required. However, some recursive functions may be converted to iterative definitions simply by using an iterative construct.

Recursion is explained further with examples such as computing factorial of a given number, computing GCD (Greatest Common Divisor), solving Towers of Hanoi problem, raising a number to a given power etc.

/*Recursive Definition*/

int factorial(int n)

{if(n==0)

return 1;

else

return(n*factorial(n-1));

}

As the above definition implies, computing a factorial using recursion is similar to computing method performed manually. The recursive function may be converted to non-recursive/iterative function as follows:

/*Non-Recursive Definition*/

int factorial(int n)

{int i,res=1;

for(i=n;i>=1;i–)

res=res*i;

return(res);

}

If we compare the recursive definition with the iterative one, we note that recursion is eliminated by using a for loop for operating n times restoring the value at each call in a variable called res. Thus, we may write a recursive algorithm considering the basic step required to sort out a given problem.

This problem is all about shifting disks from one pillar to the other pillar using a third pillar such that only one disk from the top may be moved at a time such that it is transferred to one pillar while considering that larger disk should be at the bottom of smaller disk. Recursion is used to solved Towers of Hanoi problem, since it involves repetitive shifting of disks from one pillar to the other. The ‘C’ recursive function for the same is given below with the output to trace the execution of the program:

void hanoi(int num_disks,char *src,char *tmp,char *trgt)

{

if(num_disks==1)

{printf(“nMove disk from %s to %s”,src,trgt);

}

else

{

hanoi(num_disks-1,src,trgt,tmp);

printf(“nMove disk from %s to %s”,src,trgt);

hanoi(num_disks-1,tmp,src,trgt);

}

}

To compute the greatest common divisor of two given numbers x and y, if x is lesser than y, then GCD is invoked with alternate set of arguments. If the second argument y=0, the first argument x is returned, otherwise GCD function is called with the arguments as y and xmody. The ‘C’ function for computing GCD is given below:

/*Recursive function to compute GCD*/

int GCD(int x,int y)

{

if(y==0)

return x;

else if(x<y)

return GCD(y,x);

else

return GCD(y,x%y);

}

The power of a given number may be computed by using the following function, f(x,n):

f(x,n) = 1 ; if n=0

x * x^{n-1} ; if n>0

/*Recursive definition to computer power of a given number*/

int power(int x,int n)

{

if(n==0)

return 1;

else

return(x * power(x,n-1));

}