Design & Analysis of
Algorithms
Lecture#05
Recursion, Recurrence Relations,
Homogeneous Equations, Master Method,
Substitution Method, Recursion Tree
Lecture
Contents
Recursive Functions
Recurrence Relations (Idea, Initial
Condition)
Recurrence Relations (Tower of Hanoi)
Homogeneous Recurrence Solutions
Solution for Fibonacci sequence
Master Method
Recurrence Tree
Substitution Method
Recursi
on
Recursive Functions …
Example
Recursive Functions
Binary(x, y)
Defining Binary() function
Recursive Functions …….
sum(arr[1…n])
Defining sum(arr) function
Recursive Functions …
Fibonacci (n)
Defining Fibonacci(n)
function
T(n)=T(n−1)+T(n−2)
+O(1)
T(n) = 2T(n-1)+c
Recursive Functions …….
gcd(x, y)
Defining HCF or
GCD () function
T(n)=T(n/b)+O(1)
Recursive Function
……. XPower(X,
Defining p p)
function
Recursive Functions … What makes
them work?
Recursion works only when a problem has a recursive structure
i.e. the problem's solution is similar for a large input size as
well as a small input size
If reducing the input size causes the solution to look different,
then it will be hard to use recursion
However, for the same reason, it can be hard to use loops too
Loops also depend on doing the same thing over and over, but on,
say, a different index of an array, or a different node in a linked
list
Also, you must be able to use the solutions of the small problem to
help solve the
larger one
Fortunately, many problems exhibit this kind of behavior. If you
can write it in a loop, there are ways to convert it to recursion
Recurren
ce
When an Algorithm contains a recursive call to itself its running
time can often be described by a recurrence
A recurrence is an equation or inequality that describes a function
in terms of its value on smaller inputs
A recurrence equation defines a function, say T(n) in terms of its
own value at one or more integer smaller than n
Cost of any recursive algorithm is equal to cost of statements
before/after recursive call plus decrement of n (input size) in
recursive call. For example, T(n) = 1 + T(n-1)
(above) shows a recurrence in which a problem of size n is
presented as the same problem with size n-1 + constant cost (1)
Recurrence
Relations
A recurrence relation
expresses an in terms
of a sequence {an} is an equation that
of one or more previous terms of same
sequence (a0, a1, a2, …, an-1), for all integer n ≥ n0.
Examples:
1. an = 2an-1 + an-2 for all n ≥ 3
2. an = 2an-1 + 1 for all n ≥ 2
3. an = 2an-1 + 5n for all n ≥ 2
Recursive Relation … Another
Example
Recurrence Relations … Initial
Condition
Many sequences can be a solution for the same recurrence
relation.
The initial conditions for a sequence specify the terms before
n0 (before the recurrence relation takes effect).
The recurrence relations together with the initial
conditions uniquely determines the sequence
Recurrence Relations … Tower
of Hanoi
Example:
The game of Hanoi Tower is to play with a set of disks of
graduated size with holes in their centers and a playing board
having three spokes for holding the disks.
Tower of Hanoi …
Recurrence
The object of the game is to transfer all the disks from spoke A to spoke C by
moving one disk at a time without placing a larger disk on top of a smaller one.
What is the minimal number of moves required when there are n disks?
Observation:
Say we need an moves to transfer n disks to be moved from spoke
A to spoke C.
Idea is simple:
First move n-1 disks from spoke A to B requiring
an-1 moves Then move nth disk from spoke A to C
requiring 1 move
Then move n-1 disks from spoke B to C requiring
an-1 moves Total Moves, an = an-1 + 1 + an-1 = 2an-1
Tower of Hanoi …
Recurrence
Solution:
a1 = 2a0 + 1for n=1 as per general rule
Similarly
a2 = 2a1 + 1 = 2 (2a0 + 1) + 1 = 4a0 + 3
a3 = 2a2 + 1 = 2 (2a1 + 1) + 1 = 4a1 + 3 = 4(2a0 + 1) +
3 = 8a0 + 7
Inspecting all above statements, we can
observe an = 2na0 + 2n-1
but we know that a0 is 0 (why?)
Hence
an = 0 + 2n-1
an = 2n-1
Recursion
Tree
This method of solving recurrences is
quite simple
Following are the steps to follow:
1. Expand the recurrence into a tree
2. Sum the cost of recurrences at every level of
tree
3. Simplify the sum
Recursion Tree …
Example
Let T(n) = 3T(n/4)+cn2 is the given recurrence
relation with some constant c
We can expand it into a tree
Recursion Tree … Example …
continue
Let T(n) = 3T(n/4)+cn2 is the given recurrence
relation with some constant c
Expanding T(n/4), we get
T(n/4) = 3T(n/16)+c(n/4)2
Recursion Tree … Example …
continue
Recursion Tree … Example
… Sum
Recursion Tree … Example
…
T(n)Sum
= cn +3c(n/4) +9c(n/16) +….
2 2 Terms + The cost of
2
T(1)s
= cn2 (1+(3/16)+(3/16)2+(3/16)3+ ….) +
= cn2 (Sum of geometric progression with a=1, r = 3/16, n=number of terms as
above)
Recursion Tree … Example
… Sum
Homogeneous Recurrence Relations
Solutions
If the given recurrence relation is in the form of a = Aa + Ba
n n-1 n-2
then for real values A and B we can construct a quadratic
equation as:s2 – As – B = 0
Now solving the quadratic equation as above, we solve the
recurrence as:
Case 1: if both roots are real and distinct then
Solution is: an = α(s1)n + β(s2)n
Note: Values of α and β can be determined if we are given values
of a0 and a1 as initial condition (true for all three cases)
Recurrence Relations … Initial
Condition
Equations of form a = 2a - a are called homogeneous linear
n n-1 n-2
recurrences.
Say an = 2an-1 - an-2 for all n ≥ 2 is a homogeneous linear
recurrence, values of a0 and a1 will be initial condition
Homogeneous Recurrence Relations
Solutions
Case 2: if we have exactly one real root, then
Solution is: an = αsn + βnsn
Case 3: If we have two complex conjugate roots in polar form
as: s1=r𝜃 and s2=r(-𝜃), then
Solution is: an = rn (αcos(n𝜃) + β sin(n𝜃))
Homogeneous Recurrence Relations
Solutions
Example:
Solve the recurrence an = 5an-1 - 6an-2 with a0 =1 and a1 = 4.
Forming characteristic equation, we get s2 – 5s + 6 = 0, solving
the equation we get, s = 3, 2
Since both roots of equation are real and distinct, hence solution
is of the form an
= α3n + β2n
Still there are two unknown values, α and β. To find out
their values use following equations:
α + β = a0
3α + 2β = a1
Recurrence Relations … Solution
Example
Example:
Solve the recurrence an = 6an-1 - 9an-2 with a0 =4
and a1 = 6.
Hint: both roots values are
same.
Homogeneous Recurrence Relations
Solutions
Example:
Solve the recurrence an = 2an-1 - 2an-2 with a0 =1
and a1 = 3.
Hint: both roots values are complex and
conjugate.
Homogeneous Recurrence …
Fibonacci
Example:
Series
an = an-1 + an-2 with a0 = 0 and
a1 = 1 Solution:
Same method that we
established for homogeneous
recurrences
Substitution
Method
Substitution method is simplest method to solve
recurrences
It uses iterative substitution of values while solving the
recurrence
Values are substituted enough number of times
such that a pattern is the terms is revealed
Once the pattern is identified and verified, recurrence
is evaluated till its terms are exhausted (total number
of iterations are reached)
Solution is then presented as running time
Substitution Method …
Example
Say we have a
recurrence as: T(n) =
Rough Area
Substituting n/2 in place of n in
2T(n/2)+4n, T(1)=4
original recurrence, we get
T(n/2) = 2 T(n/22)+4(n/2)
Solution Building
Substituting n/22 in place of n in
T(n) = 2T(n/2)+4n original recurrence, we get
Substituting the value of T(n/22) = 2 T(n/23)+4(n/22)
T(n/2), we get
T(n) = 2[2
T(n/22)+4(n/2)] + 4n
T(n) = 22T(n/22) + 4n +
4n
Substituting the value of
T(n/22), we get
T(n) = 22 [2 T(n/23)+4(n/22)] + 4n
3 3
Substitution Method … Example …
continue
T(n) = 2 T(n/2 ) + 4n + 4n + 4n
3 3
Rough Area
Substituting the value of T(n/23), we
Substituting n/2 in place of n in
3
original recurrence, we get
get T(n/23) = 2 T(n/24)+4(n/23)
T(n) = 23[2 T(n/24)+4(n/23)]+ 4n +
4n + 4n T(n) = 24T(n/24) + 4n + 4n +
4n +=
T(n) 4n2iT(n/2i) + i4n … Generic Pattern
Pattern
How manyin all above
levels willexpansion
expandedis:
in all until we
reach T(1)?
Note: T(1)=4 and there is nothing else to
expand i
i.e n/2 =
As per generic pattern, T(n/2i) = T(1)
. 1 n =
i.
Taking2log
i (base 2) on both sides,
e.
we get
Substitution Method … Example …
continue
Substituting the value of i in generic
pattern, we get T(n) = 2iT(n/2i) + i4n
… Generic Pattern
T(n) = 2log (n)T(n/2(log n) ) + (log
n)4n T(n) = nT(n/n) + (log
T(n)
n)4n = 4n + // substituting the value of
4n(log n) T(n)
T(n) = nT(1) =
+ 4n(log n)T(1)
4n + 4n(log n)
T(n) = O(n log
(n))