Scribd
Upload
17 views

Recursion in C-2

Recursion involves defining a problem in terms of smaller instances of the same problem. It solves problems by breaking them down into smaller sub-problems until reaching a base case that can be solved directly. When implementing recursion in code, a function calls itself to solve the smaller sub-problems, with base cases terminating the recursion. Recursion uses a stack to remember the state at each sub-problem so it can return results back up the call stack.

Uploaded by

Atharv Gupta
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
17 views

Recursion in C-2

Recursion involves defining a problem in terms of smaller instances of the same problem. It solves problems by breaking them down into smaller sub-problems until reaching a base case that can be solved directly. When implementing recursion in code, a function calls itself to solve the smaller sub-problems, with base cases terminating the recursion. Recursion uses a stack to remember the state at each sub-problem so it can return results back up the call stack.

Uploaded by

Atharv Gupta
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/ 17

Recursion

What is recursion?

• Sometimes, the best way to solve a problem


is by solving a smaller version of the exact
same problem first
• Recursion is a technique that solves a
problem by solving a smaller problem of the
same type
When you turn this into a program, you end
up with functions that call themselves
(recursive functions)
int f(int x)
{
int y;

if(x==0)
return 1;
else {
y = 2 * f(x-1);
return y+1;
}
}
Problems defined recursively
• There are many problems whose solution
can be defined recursively
Example: n factorial
1 if n = 0
n!= (recursive solution)
(n-1)!*n if n > 0

1 if n = 0
n!= (closed form solution)
1*2*3*…*(n-1)*nif n > 0
Coding the factorial function

• Recursive implementation
int Factorial(int n)
{
if (n==0) // base case
return 1;
else
return n * Factorial(n-1);
}
Coding the factorial function
(cont.)
• Iterative implementation
int Factorial(int n)
{
int fact = 1;

for(int count = 2; count <= n; count++)


fact = fact * count;

return fact;
}
Recursion vs. iteration
• Iteration can be used in place of recursion
– An iterative algorithm uses a looping construct
– A recursive algorithm uses a branching structure
• Recursive solutions are often less efficient, in
terms of both time and space, than iterative
solutions
• Recursion can simplify the solution of a problem,
often resulting in shorter, more easily understood
source code
How do I write a
recursive function?
• Determine the size factor
• Determine the base case(s)
(the one for which you know the answer)
• Determine the general case(s)
(the one where the problem is expressed as a
smaller version of itself)
• Verify the algorithm
(use the "Three-Question-Method")
Recursive binary search
• Non-recursive implementation
template<class ItemType>
void SortedType<ItemType>::RetrieveItem(ItemType& item, bool& found)
{
int midPoint;
int first = 0;
int last = length - 1;

found = false;
while( (first <= last) && !found) {
midPoint = (first + last) / 2;
if (item < info[midPoint])
last = midPoint - 1;
else if(item > info[midPoint])
first = midPoint + 1;
else {
found = true;
item = info[midPoint];
}
}
Recursive binary search (cont’d)
template<class ItemType>
bool BinarySearch(ItemType info[], ItemType& item, int first, int last)
{
int midPoint;
if(first > last) // base case 1
return false;
else {
midPoint = (first + last)/2;
if(item < info[midPoint])
return BinarySearch(info, item, first, midPoint-1);
else if (item == info[midPoint]) { // base case 2
item = info[midPoint];
return true;
}
else
return BinarySearch(info, item, midPoint+1, last);
}
}
How is recursion implemented?

• What happens when a function gets called?


int a(int w)
{
return w+w;
}

int b(int x)
{
int z,y;
……………… // other statements
z = a(x) + y;
return z;
}
What happens when a function is
called? (cont.)

• An activation record is stored into a stack


(run-time stack)
1) The computer has to stop executing function b and
starts executing function a
2) Since it needs to come back to function b later, it
needs to store everything about function b that is
going to need (x, y, z, and the place to start executing
upon return)
3) Then, x from a is bounded to w from b
4) Control is transferred to function a
What happens when a
function is called? (cont.)

• After function a is executed, the activation


record is popped out of the run-time stack
• All the old values of the parameters and
variables in function b are restored and the
return value of function a replaces a(x) in
the assignment statement
What happens when a recursive
function is called?
• Except the fact that the calling and called functions have
the same name, there is really no difference between
recursive and nonrecursive calls

int f(int x)
{
int y;
if(x==0)
return 1;
else {
y = 2 * f(x-1);
return y+1;
}
}
2*f(2)

2*f(1)

2*f(1)

=f(0)

=f(1)

=f(2)

=f(3)
Deciding whether to use a
recursive solution
• When the depth of recursive calls is
relatively "shallow"
• The recursive version does about the same
amount of work as the nonrecursive version
• The recursive version is shorter and simpler
than the nonrecursive solution

You might also like