Design and Analysis of
Algorithms
Recursive algorithms
Department of Computer Science
Recursive definitions
A recursive definition is one in which something is
defined in terms of itself
Almost every algorithm that requires looping can
be defined iteratively or recursively
All recursive definitions require two parts:
Base case
Recursive step
The recursive step is the one that is defined in
terms of itself
The recursive step must always move closer to
the base case
2
Recursive algorithm
A recursive algorithm solves the problem by
possibly using the result of applying itself to a
simpler problem
Example: Draw this picture
3
General Recursive Design Strategy
Identify the base case(s) (for direct solution)
Devise a problem splitting strategy
Subproblems must be smaller
Subproblems must work towards a base case
Devise a solution combining strategy
4
Requirements for Recursive Solution
At least one “small” case that you can solve
directly
A way of breaking a larger problem down into:
One or more smaller subproblems
Each of the same kind as the original
A way of combining subproblem results into an
overall solution to the larger problem
5
Recursive Thinking
Recursion is:
A problem-solving approach, that can ...
Generate simple solutions to ...
Certain kinds of problems that ...
Would be difficult to solve in other ways
Recursion splits a problem:
Into one or more simpler versions of itself
6
Recursive Thinking:
The General Approach
1. if problem is “small enough”
2. solve it directly
3. else
4. break into one or more smaller
subproblems
5. solve each subproblem recursively
6. combine results into solution to whole
problem
7
Recursive Thinking
Strategy for searching a sorted array:
1. if the array is empty
2. return -1 as the search result (not present)
3. else if the middle element == target
4. return subscript of the middle element
5. else if target < middle element
6. recursively search elements before middle
7. else
8. recursively search elements after the middle
8
Recursive Design Example
Recursive algorithm for finding length of a string:
1. if string is empty (no characters)
2. return 0 base case
3. else recursive case
4. compute length of string without first character
5. return 1 + that length
Note: Not best technique for this problem; illustrates the
approach.
9
Recursive algorithm Properties
A recursive algorithm solves the large problem
by using its solution to a simpler sub-problem
divide and conquer approach
Eventually the sub-problem is simple enough
that it can be solved without applying the
algorithm to it recursively
This is called the ‘base case’
10
Key Components of a Recursive Algorithm
Design
1. What is a smaller identical problem(s)?
Decomposition
2. How are the answers to smaller problems
combined to form the answer to the larger
problem?
Composition
3. Which is the smallest problem that can be solved
easily (without further decomposition)?
Base/stopping case
11
Recursion
A recursive procedure can often be analyzed
by solving a recursive equation
Basic form:
T(n) = if (base case) then some constant
else ( time to solve subproblems +
time to combine solutions )
Result depends upon
how many subproblems
how much smaller are subproblems
how costly it is to combine solutions (coefficients)
12
Example: Factorial Function
The factorial function: multiply together all
numbers from 1 to n.
denoted n!
n!=n*(n-1)*(n-2)*…2*1
n!= n*(n-1)! if n>0 General case: Uses a solution to
a simpler sub-problem
1 if n==0 Base case: Solution is given
directly
13
public static int factorial(int n)
Execution Trace {
int fact;
if (n > 1) // recursive case (decomposition)
fact = factorial(n – 1) * n; (composition)
(decomposition) else // base case
fact = 1;
return fact;
}
factorial(4)
factorial(3) 4
14
public static int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
fact = factorial(n – 1) * n; (composition)
else // base case
(decomposition) fact = 1;
return fact;
}
factorial(4)
factorial(3) 4
factorial(2) 3
15
public static int factorial(int n)
Execution Trace {
int fact;
if (n > 1) // recursive case (decomposition)
fact = factorial(n – 1) * n; (composition)
(decomposition) else // base case
fact = 1;
return fact;
}
factorial(4)
factorial(3) 4
factorial(2) 3
factorial(1) 2
16
public static int factorial(int n)
Execution Trace {
int fact;
if (n > 1) // recursive case (decomposition)
fact = factorial(n – 1) * n; (composition)
(composition) else // base case
fact = 1;
return fact;
}
factorial(4)
*
factorial(3) 4
*
factorial(2) 3
*
factorial(1) ->1 2
17
public static int factorial(int n)
{
Execution Trace int fact;
if (n > 1) // recursive case (decomposition)
fact = factorial(n – 1) * n; (composition)
else // base case
(composition) fact = 1;
return fact;
}
factorial(4)
*
factorial(3) 4
*
factorial(2) ->2 3
18
public static int factorial(int n)
Execution Trace {
int fact;
if (n > 1) // recursive case (decomposition)
fact = factorial(n – 1) * n; (composition)
(composition) else // base case
fact = 1;
return fact;
}
factorial(4)
*
factorial(3) ->6 4
19
public static int factorial(int n)
Execution Trace {
int fact;
if (n > 1) // recursive case (decomposition)
fact = factorial(n – 1) * n; (composition)
(composition) else // base case
fact = 1;
return fact;
}
factorial(4) -> 24
20
Improved factorial Method
public static int factorial(int n)
{
int fact=1; // base case value
if (n > 1) // recursive case (decomposition)
fact = factorial(n – 1) * n; // composition
// else do nothing; base case
return fact;
}
21
Example: Palindrome
Describe a palindrome recursively ( a palindrome
is a word that has the same spelling both forward
and backwards e.g. bob)
Base case:
An empty string is a palindrome
A string of one character is a palindrome
Recursive step
If S is a palindrome, then aSb is also a palindrome if
a=b
22
How Recursion Works
To truly understand how recursion works we need
to first explore how any function call works.
When a program calls a subroutine (function) the
current function must suspend its processing.
The called function then takes over control of the
program.
When the function is finished, it needs to return to
the function that called it.
The calling function then ‘wakes up’ and continues
processing.
23
How Recursion Works
One important point in this interaction is that,
unless changed through call-by- reference, all local
data in the calling module must remain unchanged.
Therefore, when a function is called, some
information needs to be saved in order to return
the calling module back to its original state (i.e., the
state it was in before the call).
We need to save information such as the local
variables and the spot in the code to return to after
the called function is finished.
24
How Recursion Works
To do this we use a stack.
Before a function is called, all relevant data is
stored in a stackframe.
This stackframe is then pushed onto the system
stack.
After the called function is finished, it simply pops
the system stack to return to the original state.
By using a stack, we can have functions call other
functions which can call other functions, etc.
Because the stack is a first-in, last-out data
structure, as the stackframes are popped, the data
comes out in the correct order.
25
Limitations of Recursion
Recursive solutions may involve extensive
overhead because they use calls.
When a call is made, it takes time to build a
stackframe and push it onto the system stack.
Conversely, when a return is executed, the
stackframe must be popped from the stack and the
local variables reset to their previous values – this
also takes time.
Every time we make a call, we must use some of
the memory resources to make room for the
stackframe.
26
Recurrences
The expression:
c n 1
T ( n)
2T c n 1
n
2
is a recurrence.
Recurrence: an equation that describes a
function in terms of its value on smaller functions
27
Recurrence Examples
0 n0 0 n0
s ( n) s ( n)
c s(n 1) n 0 n s(n 1) n 0
n 1
c c n 1
T ( n) T ( n)
2T n c n 1 n
2 aT cn n 1
b
28
Solving Recurrences
Recurrences can be solved by the following
methods
Substitution method
Iteration method
Master method
Recursive tree method
29
The substitution method
A.k.a. the “making a good guess method”
Guess the form of the answer, then use induction
to find the constants and show that solution works
Examples:
T(n) = 2T(n/2) + (n) T(n) = (n lg n)
T(n) = 2T(n/2) + n T(n) = (n lg n)
T(n) = 2T(n/2+ 17) + n (n lg n)
30
The Iteration method
Another option for solving recurrences the
“iteration method”
Expand the recurrence
Work some algebra to express as a summation
Evaluate the summation
31
The Iteration method
T(n) = c n 1
n
2T(n/2) + c T (n) 2T
c n 1
2(2T(n/2/2) + c) + c 2
22T(n/22) + 2c + c
22(2T(n/22/2) + c) + 3c
23T(n/23) + 4c + 3c
23T(n/23) + 7c
23(2T(n/23/2) + c) + 7c
24T(n/24) + 15c
…
2kT(n/2k) + (2k - 1)c
32
The Iteration method
So far for n > 2k we have
T(n) = 2kT(n/2k) + (2k - 1)c
What if k = lg n?
T(n) = 2lg n T(n/2lg n) + (2lg n - 1)c Note: 2lg n=n
= n T(n/n) + (n - 1)c
= n T(1) + (n-1)c
= nc + (n-1)c = (2n - 1)c
c n 1
n
T (n) 2T
c n 1
2
33
Proving a Recursive Method
Correct
Recall Proof by Induction:
1. Prove the theorem for the base case(s): n=0
2. Show that:
If the theorem is assumed true for n,
Then it must be true for n+1
Result: Theorem true for all n ≥ 0.
34
Proving a Recursive Method Correct
Recursive proof is similar to induction:
1. Show base case recognized and solved
correctly
2. Show that
If all smaller problems are solved correctly,
Then original problem is also solved
correctly
3. Show that each recursive case makes
progress towards the base case
terminates properly
35
Recursive Versus Iterative
Methods
All recursive algorithms/methods
can be rewritten without recursion.
Iterative methods use loops instead of recursion
Iterative methods generally run faster and use
less memory--less overhead in keeping track of
method calls
36
Recursion Versus Iteration
Recursion and iteration are similar
Iteration:
Loop repetition test determines whether to exit
Recursion:
Condition tests for a base case
Can always write iterative solution to a
problem solved recursively, but:
Recursive code often simpler than iterative
Thus easier to write, read, and debug
37
Efficiency of Recursion
Recursive method often slower than iterative;
why?
Overhead for loop repetition smaller than
Overhead for call and return
If easier to develop algorithm using recursion,
Then code it as a recursive method:
Software engineering benefit probably outweighs
...
Reduction in efficiency
Don’t “optimize” prematurely!
38
So When Should You Use Recursion?
Solutions/algorithms for some problems are
inherently recursive
iterative implementation could be more
complicated
When efficiency is less important
it might make the code easier to understand
Bottom line is about:
Algorithm design
Tradeoff between readability and efficiency
39
Towers of Hanoi: Description
Goal: Move entire tower to another peg
Rules:
1. You can move only the top disk from a peg.
2. You can only put a smaller on a larger disk
(or on an empty peg)
40
Towers of Hanoi: Solution Strategy
41
Towers of Hanoi: Solution Strategy
42
Towers of Hanoi: Recursion Structure
move(n, src, dst, tmp) =
if n == 1: move disk 1 from src to dst
otherwise:
move(n-1, src, tmp, dst)
move disk n from src to dst
move(n-1, tmp, dst, src)
43
Computing Powers
The power function, p(x,n)=xn, can be defined
recursively:
1 if n 0
p ( x, n )
x p( x, n 1) else
This leads to a power function that runs in O(n)
time (for we make n recursive calls).
We can do better than this, however.
44
Recursive Squaring
We can derive a more efficient linearly recursive
algorithm by using repeated squaring:
1 if x 0
p( x, n) x p( x, (n 1) / 2) if x 0 is odd
2
p( x, n / 2) 2 if x 0 is even
For example,
24 = 2(4/2)2 = (24/2)2 = (22)2 = 42 = 16
25 = 21+(4/2)2 = 2(24/2)2 = 2(22)2 = 2(42) = 32
26 = 2(6/ 2)2 = (26/2)2 = (23)2 = 82 = 64
27 = 21+(6/2)2 = 2(26/2)2 = 2(23)2 = 2(82) = 128. 45
A Recursive Squaring Method
Algorithm Power(x, n):
Input: A number x and integer n = 0
Output: The value xn
if n = 0 then
return 1
if n is odd then
y = Power(x, (n - 1)/ 2)
return x · y ·y
else
y = Power(x, n/ 2)
return y · y
46
Analyzing the Recursive Squaring
Method
Algorithm Power(x, n):
Input: A number x and
integer n = 0
Output: The value xn Each time we make a
recursive call we halve the
if n = 0 then
value of n; hence, we make
return 1 log n recursive calls. That
if n is odd then is, this method runs in
y = Power(x, (n - 1)/ 2) O(log n) time.
return x · y · y
else It is important that we
used a variable twice
y = Power(x, n/ 2)
here rather than calling
return y · y the method twice.
47
Conclusion
A recursive solution solves a problem by solving a
smaller instance of the same problem.
It solves this new problem by solving an even
smaller instance of the same problem.
Eventually, the new problem will be so small that
its solution will be either obvious or known.
This solution will lead to the solution of the original
problem.
48
