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
intUP WITH
f(int x) FUNCTIONS THAT CALL THEMSELVES
{ (RECURSIVE FUNCTIONS)
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")
THREE-QUESTION VERIFICATION METHOD
The Base-Case Question:
Is there a nonrecursive way out of the function, and
does the routine work correctly for this "base" case?
The Smaller-Caller Question:
Does each recursive call to the function involve a
smaller case of the original problem, leading inescapably
to the base case?
The General-Case Question:
Assuming that the recursive call(s) work correctly,
does the whole function work correctly?
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