Analysis of Recursive Algorithms

What is a recursive algorithm?

Example: Factorial

n! = 1•2•3...n and 0! = 1 (called initial case)

So the recursive defintiion n! = n•(n-1)!

 

Algorithm F(n)

if n = 0 then return 1 // base case

else F(n-1)•n // recursive call

 

 

 

Basic operation? multiplication during the recursive call

Formula for multiplication

M(n) = M(n-1) + 1

is a recursive formula too. This is typical.

 

We need the initial case which corresponds to the base case

M(0) = 0

There are no multiplications

 

Solve by the method of backward substitutions

M(n) = M(n-1) + 1

= [M(n-2) + 1] + 1 = M(n-2) + 2  substituted M(n-2) for M(n-1)

= [M(n-3) + 1] + 2 = M(n-3) + 3  substituted M(n-3) for M(n-2)

... a pattern evolves

= M(0) + n

= n

Not surprising!

Therefore M(n) ε Θ(n)

Procedure for Recursive Algorithm

1. Specify problem size

2. Identify basic operation

3. Worst, best, average case

4. Write recursive relation for the number of basic operation. Don't forget the initial conditions (IC)

5. Solve recursive relation and order of growth

 

Stop here?

Example: Tower Hanoi

Explain the problem using figure

 

Demo and show recursion

 

1. Problem size is n, the number of discs

2. The basic operation is moving a disc from rod to another

3. There is no worst or best case

4. Recursive relation for moving n discs

M(n) = M(n-1) + 1 + M(n-1) = 2M(n-1) + 1

IC: M(1) = 1

5. Solve using backward substitution

M(n) =  2M(n-1) + 1

= 2[2M(n-2) + 1] +1 = 22M(n-2) + 2+1

=22[2M(n-3) +1] + 2+1 = 23M(n-3) + 22 + 2 + 1

...

M(n) = 2iM(n-i) + ∑j=0-i2j = 2iM(n-i) + 2i-1

...

M(n) = 2n-1M(n-(n-1)) + 2n-1-1 = 2n-1M(1) + 2n-1-1 = 2n-1 + 2n-1-1 = 2n-1

 

M(n) ε Θ(2n)

 

Terrible. Can we do it better?

 

Where did the exponential term come from? Because two recursive calls are made. Suppose three recursive calls are made, what is the order of growth.

 

Lesson learned: Be careful of the recursive algorithm, they can grow exponential.

 

Especial if the problem size is measured by the level of the recursive tree and the operation count is total number of nodes.

 

Example: Binary Representation

Algorithm BinRec(n)

if n = 1 then return 1

else return BinRec(floor(n/2)) + 1

 

 

 

1. Problem size is n

2. Basic operation is the addition in the recursive call

3. There is no difference between worst and best case

4. Recursive relation including initial conditions

A(n) = A(floor(n/2)) + 1

IC A(1) = 0

5. Solve recursive relation

The division and floor function in the argument of the recursive call makes the analysis difficult.

We could make the variable substitution, n = 2k, could get rid of the definition,

 but the substitution skips a lot of values for n.

The smoothness rule (see appendix B) says that is ok.

 

Smoothness rule

T(n) eventually non-decreasing and f(n) be smooth {eventually non-decreasing and f(2n) ε Θ(f(n))}

if T(n) ε Θ(f(n)) for n powers of b then T(n) ε Θ(f(n)) for all n.

 

Works for O and Ω.

 

substitute n = 2k  (also k = lg(n))

A(2k) = A(2k-1) + 1 and IC A(20) = 0

 

A(2k) = [A(2k-2) + 1] + 1 = A(2k-2) + 2

= [A(2k-3) + 1] + 2 = A(2k-3) + 3

...

= A(2k-i) + i

...

= A(2k-k) + k

A(2k) = k

 

Substitute back k = lg(n)

A(n) = lg(n) ε Θ(lg n)

 

Example: Fibonacci Numbers Sequence

A classic example for more elaborate recursion relations.

 

Fibonacci Sequence: 0, 1, 1 2, 3, 5, 8, 13, 21, 34, ...

Fibonacci (1202) proposed for the growth of rabbits

Can be defined by the simple recurrence

F(n) = F(n-1) + F(n-2)  for  n > 1

IC: F(0) = 0 and F(1) = 1 (why do we need two ICs)

 

Homogenous second-order linear recurrence with constant coefficients

ax(n) + bx(n-1) + cx(n-2) = 0

Homogenous because the recurrence equals zero.

Why second-order linear? Substitute the proposed solution x(n) = rn

a rn + b rn-1 + c rn-2 = 0

divide by rn

a + b r + c r2 = 0, characteristic equation is a second order polynomial.

The real roots are solutions

x(n) = αr1n + βr2n

α and β are determined from the

 

Apply to Fibonacci Recursion

 F(n) - F(n-1) - F(n-2) = 0, homogenous second order with constant coefficients

  r2 - r - 1 = 0, characteristic equation

r1,2 = (1 ± √5)/2 = φ or φ' { φ = (1+√5)/2 and φ' = (1-√5)/2}

The general form of the solution

F(n) = αφn + βφ' n where α and β are unknows

Using the ICs

α  +  β   = 0

φα + φ'β = 1

Solve by substituting the first equation into the second, get α = 1/√5 and β = -1/√5

So 

F(n) = 1/√5 (φn - φ' n) = φn/√5 rounded to the nearest integer

 

Example: Recursive Algorithm for Fibonacci Numbers

Algorithm F(n)

if n ≤ 1 then return n

else return F(n-1) + F(n-2)

 

 

 

1. Problem size is n, the sequence number for the Fibonacci number

2. Basic operation is the sum in recursive call

3. No difference between worst and best case

4. Recurrence relation

A(n) = A(n-1) + A(n-2) + 1

IC: A(0) = A(1) = 0

or

A(n) - A(n-1) - A(n-2) = 1, Inhomogeneous recurrences because of the 1

 

In general solution to the inhomogeneous problem is equal to the sum of solution to homogenous problem plus solution only to the inhomogeneous part. The undetermined coefficients of the solution for the homogenous problem are used to satisfy the IC.

 

In this case A(n) = B(n) + I(n) where

A(n) is solution to complete inhomogeneous problem

B(n) is solution to homogeneous problem

I(n) solution to only the inhomogeneous part of the problem

 

We guess at I(n) and then determine the new IC for the homogenous problem for B(n)

 

For this problem the correct guess is I(n) = 1

 

substitute A(n) = B(n) -1  into the recursion and get

B(n) - B(n-1) - B(n-2) = 0 with IC B(0) = B(1) = 1

 

The same as the relation for F(n) with different IC

We do not really need the exact solution; We can conclude

A(n) = B(n) -1 = F(n+1) - 1 ε Θ(φn), exponential

 

There is the Master Theorem that give the asymptotic limit for many common problems.

Iterative algorithm

 

Algorithm Fib(n)

F[1] ← 0; F[1] ← 1

for i ← 2 to n do

F[i] ← F[i-1] + F[i-2]

return F[n]

 

Order of growth is Θ(n).

Why is it so much better then the recursive algorithm? Draw the recursive tree.