R4R
Right Place For Right Person TM
 
R4R CC TutorialsC Basic Tutorials1.6RECURSION
Previous

Home

Next

RECURSION-

A function is called ‘recursive’ if a statement within the body of a function calls the same function. Sometimes called ‘circular definition’, recursion is thus the process of defining something in terms of itself.

example of recursion--


/*factorial of a number*/
main( )
{
int a, fact ;
printf ( "\nEnter any number " ) ;
scanf ( "%d", &a ) ;
fact = rec ( a ) ;
printf ( "Factorial value = %d", fact ) ;
}
rec ( int x )
{
int f ;
if ( x == 1 )
return ( 1 ) ;
else
f = x * rec ( x - 1 ) ;
return ( f ) ;
}

And here is the output for four runs of the program
Enter any number 1
Factorial value = 1
Enter any number 2
Factorial value = 2
Enter any number 3
Factorial value = 6
Enter any number 5
Factorial value = 120

 

explanation of the program-

 In the first run when the number entered through scanf( ) is 1, let us see what action does rec( ) take. The value of a (i.e. 1) is copied into x. Since x turns out to be 1 the condition if ( x == 1 ) is satisfied and hence 1 (which indeed is the value of 1 factorial) is returned through the return statement. When the number entered through scanf( ) is 2, the ( x == 1 ) test
fails, so we reach the statement,
       f = x * rec ( x - 1 ) ;
And here is where we meet recursion. How do we handle the expression x * rec ( x - 1 )? We multiply x by rec ( x - 1 ). Since the current value of x is 2, it is same as saying that we must calculate the value (2 * rec ( 1 )). We know that the value returned by rec ( 1 ) is 1, so the expression reduces to (2 * 1), or simply 2. Thus the statement,
         x * rec ( x - 1 ) ;
evaluates to 2, which is stored in the variable f, and is returned to main( ), where it is duly printed as
       Factorial value = 2

RECURSION AND STACK

There are different ways in which data can be organized. For example, if you are to store five numbers then we can store them in five different variables, an array, a linked list, a binary tree, etc. All these different ways of organizing the data are known as data structures. The compiler uses one such data structure called stack for implementing normal as well as recursive function calls.

                                                                                                   A stack is a Last In First Out (LIFO) data structure. This means that the last item to get stored on the stack (often called Push operation) is the first one to get out of it (often called as Pop operation).

for example-

main( )
{
int a = 5, b = 2, c ;
c = add ( a, b ) ;
printf ( "sum = %d", c ) ;
}
add ( int i, int j )
{
int sum ;
sum = i + j ;
return sum ;
}
In this program before transferring the execution control to the function fun( ) the values of parameters a and b are pushed onto the stack. Following this the address of the statement printf( ) is pushed on the stack and the control is transferred to fun( ). It is necessary to push this address on the stack. In fun( ) the values of a and b that were pushed on the stack are referred as i and j. In fun( ) the local variable sum gets pushed on the stack. When value of sum is returned sum is popped up from the stack. Next the address of the statement where the control should be returned is popped up from the stack. Using this address the control returns to the printf( ) statement in main( ). Before execution of printf( ) begins the two integers that were earlier pushed on the stack arenow popped off.

 

Previous

Home

Next

R4R CC TutorialsC Basic Tutorials1.6RECURSION
Tolal:0 Click:
Show All Comments

Post Your Comments

Your Name:

Your Email ID :
Comments :
URL
  =* Enter SUM

New Updates

10:New Updates
Tutorials,examples and Interview Questions with answers
Posted By: Shashi     Posted Date:02.10.14

9:C# Tutorials,C# examples and C# Interview Questions with answers
R4R provide C# Tutorials,C# examples and C# Interview Questions with answers. Through R4R you can develop a small application and small programs.We cover C# Tutorials,C# examples and C# Interview Questions and answers for freshers as well experienced programmer.
Posted By: Shashi     Posted Date:11.17.13

8:Java/J2EE(Servlet,JSP,JNDI,Struts,Spring,Hibernate,EJB,JSF,JMS,Web-Services)
In this section R4R covers Java/J2EE(Servlet,JSP, JNDI, Struts, Spring, Hibernate, EJB,JSF,JMS,Web-Services) Tutorials with Examples.R4R provide Java/J2EE (Servlet,JSP, JNDI,Struts, Spring, Hibernate, EJB, JSF, JMS, Web-Services) Interview Questions with answers study materials for freshers and experienced.
Posted By: Shashi     Posted Date:11.13.13

7:CoreJava Tutorials , CoreJava Examples and CoreJava Interview Questions with answers
In this section R4R covers CoreJava Tutorials with CoreJava Examples. R4R covers CoreJava programming concept in easy way. R4R provide CoreJava Interview Questions with answers study materials for freshers and experienced.
Posted By: Shashi     Posted Date:11.04.13

6:Microsoft.net Technology ASP.NET,c# ,ADO.NET,WCF,WPF,Silverlight ,VB.net
R4R provides Microsoft Technologies(like ASP.NET,c# ,ADO.NET,WCF,WPF, Silverlight and VB.ne)Tutorials with Examples,programming concept and Interview Questions with answers study materials for freshers and experienced.
Posted By: Shashi     Posted Date:11.04.13

5:J2me Tutorials concept with Examples with Netbean IDE and J2ME Application Examples.
R4R cover basic J2me Tutorials concept with Examples and provide a way to develop J2me programming concept in easy way. R4R provide J2me Interview Questions with answers.R4R provide J2me Languages study materials with examples uing Netbean IDE and J2ME Application Examples.
Posted By: Shashi     Posted Date:10.30.13

4:J2me Tutorials concept with Examples ith netbean IDE and J2ME Application Examples.
R4R cover basic J2me Tutorials concept with Examples and provide a way to develop J2me programming concept in easy way. R4R provide J2me Interview Questions with answers.R4R provide J2me Languages study materials with examples uing Netbean IDE and J2ME Application Examples.
Posted By: Shashi     Posted Date:10.30.13

3:Java ebooks , Java tutorials , Java examples , Java interview questions and answers
R4R provides study materials for Java/j2EE technologies. R4R covers core java, advanced java, servlet, JSP, Struts, Spring, Hibernate, EJB, JSF, J2ME, ANT, JUnit and Some APIS .R4R also provides ebooks,tutorials,examples, interview questions and answers.
Posted By: Shashi     Posted Date:10.30.13

2:Learn basic C++ Tutorials with Examples , C++ Interview Questions with answers
R4R is a free E-learning website.You can learn basic C++ Tutorials with Examples , C++ Interview Questions with answers and also some hot topics.
Posted By: Shashi     Posted Date:10.30.13

1:C Tutorials with Example C subjective and objective interview questions and answers
R4R provide C Tutorials with Example and also provides C subjective and objective interview questions and answers.You can learn C in easy way.We cover basics of C here and give some examples.
Posted By: Shashi     Posted Date:10.30.13

R4R
R4R
R4R
R4R
R4R
R4R
R4R
R4R