Recursion

Algorithm : Design & Analysis

[3]
In the last class…
◼ Asymptotic growth rate
◼ The Sets ,  and 
◼ Complexity Class
◼ An Example: Maximum Subsequence Sum
◼ Improvement of Algorithm
◼ Comparison of Asymptotic Behavior
◼ Another Example: Binary Search
◼ Binary Search Is Optimal
Recursion
◼ Recursive Procedures
◼ Proving Correctness of Recursive Procedures
◼ Deriving recurrence equations
◼ Solution of the Recurrence equations
◼ Guess and proving
◼ Recursion tree
◼ Master theorem
◼ Divide-and-conquer
Recursion for Algorithm Recurrence
relations
◼ Computing n!
◼ if n=1 then return 1 else return Fac(n-1)*n
M(1)=0 and M(n)=M(n-1)+1 for n>0
(critical operation: multiplication)

◼ Hanoi Tower
◼ if n=1 then move d(1) to peg3 else
{ Hanoi(n-1, peg1, peg2); move d(n) to peg3; Hanoi(n-1,
peg2, peg3)
M(1)=1 and M(n)=2M(n-1)+1 for n>1
(critical operation: move)
Counting the Number of Bit
◼ Input: a positive decimal integer n
◼ Output: the number of binary digits in n’s
binary representation
Int BinCounting (int n)
1. if (n==1) return 1;
2. else
3. return BinCounting(n div 2)+(n
mod 2);
Correctness of BinCounting
◼ Proof by induction
◼ Base case: if n =1, trivial by line 1.
◼ Inductive hypothesis: for any 0<k<n, BinCounting(k)
return the correct result.
◼ Induction
◼ If n1 then line 3 is executed
◼ (n div 2) is a positive decimal integer (so, the
precondition for BinCounting is still hold), and
◼ 0<(n div 2)<n, so, the inductive hypothesis applies
◼ So, the correctness (the number of bit of n is one more
than that of (n div 2)
Complexity Analysis of BinCounting

◼ The critical operation: addition

◼ The recurrence relation

0 n =1
T ( n) = 
 T (n / 2) + 1 n 1
Solution by backward substitutions
n
By the recursion equation： T (n) = T     + 1
2
For simplicity, let n = 2 (k is a nonnegative integer ),
k

that is, k = log n

n n n
T (n) = T   + 1 = T   + 1 + 1 = T   + 1 + 1 + 1 = ......
2 4 8
 n 
T (n) = T  k  + log n = log n ( T(1)=0 )
2 
Smooth Functions
◼ Let f(n) be a nonnegative eventually non-
decreasing function defined on the set of
natural numbers, f(n) is called smooth if
f(2n)(f(n)).
◼ Note: logn, n, nlogn and n (0) are all
smooth.
◼ For example: 2nlog2n = 2n(logn+log2)(nlogn)
Even Smoother
◼ Let f(n) be a smooth function, then, for any fixed integer b2,
f(bn)(f(n)).
◼ That is, there exist positive constants cb and db and a
nonnegative integer n0 such that
dbf(n)  f(bn)  cbf(n) for nn0.

It is easy to prove that the result holds for b = 2 k ,

for the second inequality:
f (2 k n) £ c2k f (n) for k = 1, 2, 3... and n ³ n0 .
For an arbitrary integer b ³ 2, 2 k-1 £ b £ 2 k
Then, f (bn) £ f (2 k n) £ c2k f (n), we can use c2k as cb .
Smoothness Rule
◼ Let T(n) be an eventually nondecreasing function and
f(n) be a smooth function. If T(n)(f(n)) for values of
n that are powers of b(b2), then T(n)(f(n)).
Just proving the big - Oh part :
By the hypothsis : T (b k )  cf (b k ) for b k  n0 .
By the prior result : f (bn )  cb f (n) for n  n0 .
Let n0  b k  n  b k +1 ,
T (n)  T (b k +1 )  cf (b k +1 ) = cf (bb k )  ccb f (b k )  ccb f (n)
Non-decreasing
hypothesis Prior result Non-decreasing
Computing the nth Fibonacci Number
f1=1
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ......
f2=1
fn= fn-1+ fn-2
is called linear homogeneous relation of degree k.
For the special case of Fibonacci: an=an-1+an-2, r1=r2=1
Characteristic Equation
◼ For a linear homogeneous recurrence relation of degree k
an = r1an −1 + r2 an − 2 +  + rk an − k
the polynomial of degree k
x k = r1 x k −1 + r2 x k −2 ++ rk
is called its characteristic equation.

◼ The characteristic equation of linear homogeneous

recurrence relation of degree 2 is:

x 2 − r1 x − r2 = 0
Solution of Recurrence Relation
If the characteristic equation x − r1 x − r2 = 0 of the
2
◼

recurrence relation an = r1an−1 + r2 an−2 has two distinct

roots s1 and s2, then
an = us + vs
n
1
n
2
where u and v depend on the initial conditions, is the
explicit formula for the sequence.

◼ If the equation has a single root s, then, both s1 and s2 in

the formula above are replaced by s
Proof of the Solution
Remember the equation: x 2 - r1 x - r2 = 0
We need prove that: us + vs = r1an-1 + r2 an-2
n
1
n
2

us + vs = us
n
1
n
2
n-2 2
1 1 s + vs n-2 2
2 2s
= us n-2
1 (r1s1 + r2 ) + vsn-2
2 (r1s2 + r2 )
= r1us1n-1 + r2 us1n-2 + r1vs2n-1 + r2 vs2n-2
= r1 (us + vs ) + r2 (us
n-1
1
n-1
2
n-2
1 + vs n-2
2 )
= r1an-1 + r2 an-2
Return to Fibonacci Sequence
f1=1
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ......
f2=1
fn= fn-1+ fn-2 Explicit formula for Fibonacci Sequence
The characteristic equation is x2-x-1=0, which has roots:
1+ 5 1- 5
s1 = and s2 =
2 2
Note: (by initial conditions) f1 = us1 + vs2 =1 and f 2 = us1 + vs2 =1
2 2

n n
which results: 1  1+ 5  1  1− 5 
fn =   −  
5  2  5  2 
Maximum Subsequence Sum：
Divide-and-Conquer

Part 1 Part 2
the sub with largest sum may be in:
recursion

Part 1 Part 2
or:
The largest is
the result

Part 1 Part 2
T(n)=2T(n/2) +n (n=2k)
Guess the Solutions
◼ Example: T(n)=2T(n/2) +n
◼ Guess T(n) = 2T(n/2)+n
◼ T(n)O(n)?  2(cn/2 log (n/2))+n
 cnlog (n/2)+n
◼ T(n)cn, to be proved for c large enough
= cn log n – cn log 2 +n
◼ T(n)O(n2)? = cn log n – cn + n
◼ T(n)cn2, to be proved forc cn logenough
large n for c1
◼ Or maybe, T(n)O(nlogn)?
◼ T(n)cnlogn, to be proved for c large enough
Recursion Tree
T(size) nonrecursive cost
T(n) n

T(n/2) n/2 T(n/2) n/2

T(n/4) n/4 T(n/4) n/4 T(n/4) n/4 T(n/4) n/4

The recursion tree for T(n)=T(n/2)+T(n/2)+n

Recursion Tree Rules
◼ Construction of a recursion tree
◼ work copy: use auxiliary variable
◼ root node
◼ expansion of a node:
◼ recursive parts: children
◼ nonrecursive parts: nonrecursive cost

◼ the node with base-case size

Recursion tree equation
◼ For any subtree of the recursion tree,
◼ size field of root =
Σ nonrecursive costs of expanded nodes +
Σ size fields of incomplete nodes
◼ Example: divide-and-conquer:
T(n) = bT(n/c) + f(n)
◼ After kth expansion: k −1
 n i −1  n 
T (n) = b T  k  +  b f  i −1 
k

 c  i =1 c 
Evaluation of a Recursion Tree
◼ Computing the sum of the nonrecursive costs
of all nodes.
◼ Level by level through the tree down.
◼ Knowledge of the maximum depth of the
recursion tree, that is the depth at which the
size parameter reduce to a base case.
Recursion Tree
Work copy: T(k)=T(k/2)+T(k/2)+k

T(n) n T(n)=nlgn

T(n/2) n/2 T(n/2) n/2

n/2d
(size →1)

T(n/4) n/4 T(n/4) n/4 T(n/4) n/4 T(n/4) n/4

At this level: T(n)=n+2(n/2)+4T(n/4)=2n+4T(n/4)

 T(n)=3T(n/4)+(n 2)
Recursion Tree for
cn2 cn2

3
c(¼ n)2 c(¼ n)2 c(¼ n)2 cn 2
16

log4n
2
c((1/16)n)2 c((1/16)n)2 …… c((1/16)n)2 …… c((1/16)n)2  3
  cn
2
c((1/16)n)2
 16 
…… ……

…
T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) (
 n log 4 3 )
log 4 n
Note: 3 =n log 4 3
Total: (n2)
 Verifying “Guess” by Recursive Tree
log 4 n −1 i T (n)  3T ( n / 4) + cn 2
3 2
T ( n) = 
i =0
  cn + (n 4 )
 16 
log 3
 3d n / 4 + cn 2
2


3 2
i
 3d (n / 4) 2 + cn 2
    cn + (n log 4 3 )
i = 0  16  3 2
= dn + cn 2
1 16
= cn 2 + (n log 4 3 )
3 16
1−    dn 2
when d  c
 16  13
16 2
= cn + (n log 4 3 ) = O(n 2 ) Inductive hypothesis
13
 Recursion Tree for T(n)=bT(n/c)+f(n)
f(n) f(n)

b
f(n/c) f(n/c) f(n/c) bf (n / c)

b
logcn

f(n/c2) f(n/c2) f(n/c2) f(n/c2) f(n/c2) f(n/c2) f(n/c2) f(n/c2) f(n/c2) b 2 f (n / c 2 )

…… ……

…
T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) … T(1) T(1) T(1) (
 n log c b )
Note: b log c n
=n log c b
Total ?
Solving the Divide-and-Conquer
◼ The recursion equation for divide-and-conquer,
the general case:T(n)=bT(n/c)+f(n)
◼ Observations:
◼ Let base-cases occur at depth D(leaf), then n/cD=1,
that is D=lg(n)/lg(c)
◼ Let the number of leaves of the tree be L, then L=bD,
that is L=b(lg(n)/lg(c)).
◼ By a little algebra: L=nE, where E=lg(b)/lg(c), called
critical exponent.
lg n lg n lg n lg b
lg b lg n
L=b = 2lg b =2 =2
lg c
lg c lg c lg c
Divide-and-Conquer: the Solution
◼ The recursion tree has depth D=lg(n)/ lg(c), so there
are about that many row-sums.
◼ The 0th row-sum is f(n), the nonrecursive cost of the
root.
◼ The Dth row-sum is nE, assuming base cases cost 1,
or (nE) in any event.
◼ The solution of divide-and-conquer equation is the
non-recursive costs of all nodes in the tree, which is
the sum of the row-sums.
Solution by Row-sums
◼ [Little Master Theorem] Row-sums decide the
solution of the equation for divide-and-conquer:
◼ Increasing geometric series: T(n)(nE)
◼ Constant: T(n) (f(n) log n)
◼ Decreasing geometric series: T(n) (f(n))

This can be generalized to get a

result not using explicitly row-sums.
 The positive  is critical,
resulting gaps between
Master Theorem cases as well

◼ Loosening the restrictions on f(n)

◼ Case 1: f(n)O(nE-), (>0), then:
T(n)(nE)
◼ Case 2: f(n)(nE), as all node depth contribute
about equally:
T(n)(f(n)log(n))
◼ case 3: f(n)(nE+), (>0), and f(n)O(nE+),
(), then:
T(n)(f(n))
Using Master Theorem
n
Example 1 T ( n) = 9T   + n
3
b = 9, c = 3, E = 2, f ( n) = n = O ( n E −1 ),
case 1 applies, T ( n) = ( n 2 )
 2n 
Example 2 T ( n) = T   +1
 3 
3
b = 1, c = , E = 0, f ( n) = 1 = ( n 0 ),
2
case 2 applies, T ( n) = (lg n)
Using Master Theorem

n
Example 3 T (n) = 3T   + n lg n
4
b = 3, c = 4, E = log 4 3  0.793,
E + 0.21 E +1.21
f (n) = n lg n = (n ) = O(n )
case 3 applies, T (n) = (n lg n)
Looking at the Gap
◼ T(n)=2T(n/2)+nlgn
◼ a=2, b=2, E=1, f(n)=nlgn
◼ We have f(n)=(nE), but no >0 satisfies
f(n)=(nE+), since lgn grows slower that n for
any small positive .
◼ So, case 3 doesn’t apply.
◼ However, neither case 2 applies.
Home Assignment
◼ pp.143-
◼ 3.4
◼ 3.6
◼ 3.9-3.11