Scribd
Upload
15 views

Lecture11-Recursion 1

Uploaded by

pavan050605
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views

Lecture11-Recursion 1

Uploaded by

pavan050605
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

INDIAN INSTITUTE OF INFORMATION TECHNOLOGY, DESIGN AND MANUFACTURING, KANCHEEPURAM

Problem Solving and Programming


(CS1000)
Recursion

Dr. Jaishree Mayank


Assistant Professor
Department of Computer Sc. and Engg.
Recursion

A process by which a function calls itself repeatedly.


Either directly.
F calls F.
• Or cyclically in a chain.
F calls G, G calls H, and H calls F.

Used for repetitive computations in which each action is stated in


terms of a previous result.

fact(n) = n * fact (n-1)


Basis and Recursion
For a problem to be written in recursive form, two conditions are to
be satisfied:
• It should be possible to express the problem in recursive form.
• The problem statement must include a stopping condition
fact(n) = 1,= n * fact(n − 1),
if n = 0 /* Stopping criteria */
if n > 0 /* Recursive form */
Example
Factorial:
fact(n<=1) = 1
fact(n) = n * fact(n − 1), if n > 0

• Fibonacci series
(1,1,2,3,5,8,13,21,....)
Recursion execution
fact(4)
if (4 = = 1) return (1);
else return (4 * fact(3));

6
if (3 = = 1) return (1);
else return (3 * fact(2));
2
if (2 = = 1) return (1);
else return (2 * fact(1));
1
if (1 = = 1) return (1);
else return (1 * fact(0));
Recursion execution
int f (int n)
{
if(n>=0){
if (n < 2)
return (n);
else
return ( f(n − 1) + f(n − 2) );
}
}
Notable Point

Every recursive program can also be written without recursion

• Recursion is used for programming convenience, not for performance


enhancement

• Sometimes, if the function being computed has a nice recurrence form, then a
recursive code may be more readable
When you write a recursive function
• First write the terminating/base condition
• Then write the rest of the function
• Always double-check that you have both
Example:

Printing the digits of an Integer in Reverse


Example:

Printing the digits of an Integer in Reverse


void printReversed( int i )
{
if (i < 10) {
printf(“%d\n”, i);
return;

}
else {
printf(“%d”, i%10);
printReversed(i/10);
}
}
Recursion versus Iteration:

Repetition
• Iteration: explicit loop
• Recursion: repeated nested function calls
Termination
• Iteration: loop condition fails
• Recursion: base case recognized
Both can have infinite loops
How are recursive calls implemented?
What we have seen ....
• Activation record gets pushed into the stack when a function call is made.
• Activation record is popped off the stack when the function returns.
In recursion, a function calls itself.
• Several function calls going on, with none of the function calls returning back.
 Activation records are pushed onto the stack continuously.
 Large stack space required.
Activation records keep popping off, when the termination condition of
recursion is reached.
Activation records -local variables, return address, return value
Thanks
Any Questions?

You might also like