What is a recursive algorithm?

*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*)

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?

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) = 2*M*(*n*-1)
+ 1

IC: *M*(1) = 1

5. Solve using backward substitution

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

= 2[2*M*(*n*-2) + 1] +1 = 2^{2}*M*(*n*-2) + 2+1

=2^{2}[2*M*(*n*-3) +1] + 2+1 = 2^{3}*M*(*n*-3) + 2^{2} + 2 + 1

...

*M*(*n*) = 2* ^{i}M*(

...

*M*(*n*) = 2^{n}^{-1}*M*(*n-*(*n*-1)) + 2^{n}^{-1}-1 = 2^{n}^{-1}*M*(1) + 2^{n}^{-1}-1 = 2^{n}^{-1}
+ 2^{n}^{-1}-1 = 2* ^{n}*-1

*M*(*n*) ε Θ(2* ^{n}*)

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.

**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* = 2* ^{k}*, 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*(2*n*) ε Θ(*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* = 2* ^{k }* (also

*A*(2* ^{k}*) =

*A*(2* ^{k}*) = [

= [*A*(2^{k}^{-3}) + 1] + 2 = *A*(2^{k}^{-3})
+ 3

...

= *A*(2^{k}^{-i})
+ *i*

...

= *A*(2* ^{k-k}*) +

*A*(2* ^{k}*) =

Substitute back *k* = lg(*n*)

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

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)

*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*) = *r ^{n}*

*a** r ^{n}* +

divide by *r ^{n}*

*a*
+ *b* r + *c* *r*^{2} = 0, *characteristic equation* is a second
order polynomial.

The real roots are solutions

*x*(*n*) = *αr*_{1}* ^{n}* +

*α* and *β* are determined from the

Apply to Fibonacci Recursion

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

*r*^{2} - *r* - 1 = 0, characteristic equation

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

The general form of the solution

*F*(*n*) = *αφ ^{n}*
+

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}* -

**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.

**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.