CS 321-Design & Analysis of
Algorithms
Recursion
National University of Modern Languages, Islamabad
1
Recursion
Basic problem solving technique is to divide a
problem into smaller subproblems
These subproblems may also be divided into
smaller subproblems
When the subproblems are small enough to
solve directly, the process stops
A recursive algorithm is a problem solution
that has been expressed to solve subproblems
What is recursion?
A procedure that is defined in terms
of itself
In
a computer language a function
that calls itself
Recursion in Computer Science
1. Recursive data structure: A data structure that is
partially composed of smaller or simpler instances of
the same data structure.
For instance, a tree is composed of smaller trees
(subtrees) and leaf nodes, and a list may have other
lists as elements.
a data structure may contain a pointer to a variable of
the same type:
struct Node {
int data;
Node *next;
};
Recursive Data Structures
inked lists and trees are recursive data structures:
struct Node {
int data;
Node *next;
};
struct TreeNode {
int data;
TreeNode *left;
TreeNode * right;
};
ecursive data structures suggest recursive algorithms.
A mathematical look
We are familiar with
f(x) = 3x+5
How about
f(x) = 3x+5 if x > 10 or
f(x) = f(x+2) -3 otherwise
Calculate f(5)
f(x) = 3x+5 if x > 10 or
f(x) = f(x+2) -3 otherwise
f(5) = f(7)-3
f(7) = f(9)-3
f(9) = f(11)-3
f(11) = 3(11)+5
= 38
But we have not determined what f(5) is yet!
Calculate f(5)
f(x) = 3x+5 if x > 10 or
f(x) = f(x+2) -3 otherwise
f(5) = f(7)-3 = 29
f(7) = f(9)-3 = 32
f(9) = f(11)-3 = 35
f(11) = 3(11)+5
= 38
Working backwards we see that f(5)=29
Series of calls
f(5)
f(7)
f(9)
f(11)
Recursion
Recursion occurs when a function/procedure calls
itself.
Many algorithms can be best described in terms of
recursion.
Example: Factorial function
The product of the positive integers from 1 to n
inclusive is
called "n factorial", usually denoted by n!:
n! = 1 * 2 * 3 .... (n-2) * (n-1) * n
Recursive Definition of the Factorial
Function
1, if n = 1
n! =
n * (n-1)! if n > 0
5! = 5 * 4! = 5 * 24 = 120
4! = 4 * 3! = 4 * 3! = 4 * 6 = 24
3! = 3 * 2! = 3 * 2! = 3 * 2 = 6
2! = 2 * 1! = 2 * 1! = 2 * 1 = 2
1! = 1 * 0! = 1 * 0! = 1
12
Recursive Definition
of the Fibonacci Sequence
he Fibonacci numbers are a series of numbers as follows:
b(1) = 1 1, n <= 2
b(2) = 1 fib(n) = fib(n-1) + fib(n-2), n > 2
b(3) = 2
b(4) = 3
b(5) = 5
. fib(3) = 1 + 1 = 2
fib(4) = 2 + 1 = 3
fib(5) = 2 + 3 = 5
14
iterative
int main()
{
int n=5, firstTerm = 1, secondTerm = 1, nextTerm;
for (int i = 1; i <= n-2; ++i)
{ nextTerm = firstTerm + secondTerm;
cout << nextTerm << " + ";
firstTerm = secondTerm;
secondTerm = nextTerm;
}
return 0; }
15
Recursive Definition
int BadFactorial(n)
{
int x = BadFactorial(n-1);
if (n == 1)
return 1;
else
return n*x;
}
What is the value of BadFactorial(2)?
We must make sure that recursion eventually stops, otherwise
it runs forever:
Using Recursion Properly
For correct recursion we need two parts:
1. One (ore more) base cases that are not recursive,
i.e. we
can directly give a solution:
if (n==1)
return 1;
2. One (or more) recursive cases that operate on
smaller
problems that get closer to the base case(s)
return n * factorial(n-1);
The base case(s) should always be checked before the
recursive calls.
Counting Digits
Recursive definition
digits(n) = 1 if (–9 <= n <= 9)
1 + digits(n/10) otherwise
Example
digits(321) =
1 + digits(321/10) = 1 +digits(32) =
1 + [1 + digits(32/10)] = 1 + [1 + digits(3)] =
1 + [1 + (1)] =
3
Counting Digits in C++
int numberofDigits(int n) {
if ( n < 10)
return 1
else
return 1 + numberofDigits(n/10);
}
Recursion
If you want to compute f(x) but can’t compute
it directly
Assume you can compute f(y) for any value of
y smaller than x
Use f(y) to compute f(x)
For this to work, there has to be at least one
value of x for which f(x) can be computed
directly (e.g. these are called base cases)
Evaluating Exponents Recurisivley
int power(int k, int n) {
// raise k to the power n
if (n == 0)
return 1;
else
return k * power(k, n – 1);
}
Stacks
Every recursive function can be
implemented using a stack and
iteration.
Everyiterative function which uses a
stack can be implemented using
recursion.
Disadvantages
May run slower.
Compilers
Inefficient Code
May use more space.
Advantages
More natural.
Easier to prove correct.
Easier to analysis.
More flexible.
Reference
Introduction to Algorithms
Chapter # 4
Thomas H. Cormen
3rd Edition
