My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
Resources » Articles/Knowledge Sharing » Computer & Technology »
Recursion in C Language
|
The C language allows programmer to write functions that calls themselves and this is called Recursion.Let’s start with the example of computing the factorial value of an integer.Factorial value of 4 equals 4*3*2*1=24.Factorial value of 0 is defined as 1.In mathemetics ,the exclamation mark (!) is used to denote a factorial function.We may therefore define factorial function as : ( for each value of n separately)
0!=1
1!=1
2!=2*1
3!=3*2*1
4!=4*3*2*1
But it is not possible to have a list of formula for factorial value of each every integer.
Or we can design the list as shown below :
4!=4*3!
3!=3*2!
2!=2*1!
1!=1*0!
0!=1
1!=1*1=1
2!=2*1=2
3!=3*2=6
4!=4*6=24
So we can define a function which will call itselt repeatadely with 4,3,2,1 and 0 as argument ( 4 being the value whose factorial value is to be calculated )
A recursive function should have two properties-
? There must be certain argument, called base value , for which the function does not call itself.
? Each time the function calls itself, the argument must be closer to the base value.
The factorial function may be defined as – if n=0 then n!=1
else
n!=n.(n-1)!
Here 0 is the base value.
The program with recursive function to compute n! is as follows :
#include
#include
int fact(int n)
{
int x,y;
if(n==0)
return 1;
x=n-1;
y=fact(x);
return n*y;
}
void main()
{
int x;
clrscr();
printf(“\nEnter the integer whose factorial value you want :-“);
scanf(“%d”,&x);
printf(“\nThe facorial value is:-%d”,fact(x));
getch();
}
In the statement y=fact(x) the function calls itself and this is an essential ingredient of a recursive function.However the programmer must ensure that this does not lead to an endless series of calls.
Let us examine the program – The recursive function fact() is called from the calling program with argument.Suppose the value n is 3.Since n is not equal to 0 , x is set equal to 2 and fact () function is called for the second time with an argument 2.Therefore the function fact () is reentered and the function variables int x,y and the argument are reallocated.Since the execution has not yet left the first call of fact () function , the first allocation of these variables remains.Thus there are two generations of each of these variables in existence simultaneously.From any point of execution of the second call of the function only the most recent copy of the variables can be accessed.
In general , every time the function fact is entered recursively , a new set of function variables and parameter(s) is allocated and only this new set may be referenced within that call of fact function.Until the value of n becomes 0, the fact () function will not return any value but different copies of x,y and n will be created and their values will be stored in stack order.It can be represented as :-
0 - -
1 - - 1 0 -
2 - - 2 1 - 2 1 -
3 - - 3 2 - 3 2 - 3 2 -
n x y n x y n x y n x y
fact(3) fact(2) fact(1) fact(0)
Hyphen (-) means variable is created but not initialized.
When the function starts returning ( it will first return value when n becomes 0) and the values will be returned to the statement y=fact(x) .During this process the elements of the stack will be poped , recent copies of the function variables and the parameter will be deleted and the previous versions will be active.It can be represented as :-
1 0 1
2 1 - 2 1 1
3 2 - 3 2 - 3 2 2
n x y n x y n x y n x y
fact(0) fact(1) fact(2) fact(3)
Ultimately the statement return n*y will return 3*2 to the calling program, which is the factorial value of 3.
|
Responses
|
No responses found. Be the first to respond and make money from revenue sharing program.
|
|
Advertise Here
|