CSE-250 Fall 2022 - Section B - Recursion

### Recursion

#### CSE-250 Fall 2022 - Section B

Sept 23, 2022

##### Textbook: Ch. 15
Ukranian Nesting Doll Nesting Dolls Handmade Dolls | Etsy

Computational problems can be recursive too!

#### Factorial

$439!$ $= 439 \cdot 438!$

#### Factorial

Recursive Case: $n! = n \cdot (n-1)!$

Base Case: $1! = 1$

#### Factorial


def factorial(n: Int): Long =
if(n <= 1){ 1 }
else { n * factorial(n-1) }


#### Factorial

Base Case:

if(n <= 1){ 1 }

Recursive Case:

else { n * factorial(n-1) }


#### Fibonacci

1, 1, 2, 3, 5, 8, 13, 21,

#### Fibonacci

Base Cases: $\texttt{fib}(1) = 1$, $\texttt{fib}(2) = 1$

Recursive Cases: $\texttt{fib}(n) = \texttt{fib}(n-1) + \texttt{fib}(n-2)$

#### Fibonacci


def fib(n: Int): Long =
if(n < 2){ 1 }
else { fib(n-1) + fib(n-2) }


#### Fibonacci

Base Case:

if(n < 2){ 1 }

Recursive Case:

else { fib(n-1) + fib(n-2) }


Live demo!

#### Towers of Hanoi

Task: Move $n$ blocks from A to C

Base Case ($n=1$)

1. Move the block from A to C

Recursive Case ($n \geq 2$)

1. Move $n-1$ blocks from A to B
2. Move the bottom block from A to C
3. Move $n-1$ blocks from B to C

#### Towers of Hanoi


var towers = Array(new Stack(), new Stack(), new Stack())

def move(fromTower: Int, toTower: Int, numDisks: Int): Unit =
{
val otherTower = (Set(0, 1, 2) - fromTower - toTower).head

if(numDisks == 1){
moveOne(from = fromTower, to = toTower)
} else {
move(fromTower, otherTower, numDisks-1)
moveOne(from = fromTower, to = toTower)
move(otherTower, toTower, numDisks-1)
}
}


How do we get the complexity of recursive algorithms?

#### Factorial

What's the complexity? (in terms of n)


def factorial(n: Int): Long =
if(n <= 1){ 1 }
else { n * factorial(n-1) }


Idea: Write down a recursive runtime growth function

#### Factorial

What's the complexity? (in terms of n)


def factorial(n: Int): Long =
if(n <= 1){ 1 }
else { n * factorial(n-1) }


#### Factorial

$$T(n) = \begin{cases} \Theta(1) & \textbf{if } n \leq 0\\ T(n-1) + \Theta(1) & \textbf{otherwise} \end{cases}$$

#### Factorial

Base Case ($n \leq 0$) $$\Theta(1)$$

Recursive Case ($n > 0$) $$T(n-1) + \Theta(1)$$

#### Factorial

$$T(n) = \begin{cases} \Theta(1) & \textbf{if } n \leq 0\\ T(n-1) + \Theta(1) & \textbf{otherwise} \end{cases}$$

Solve for $T(n)$

#### Factorial

Solve for $T(n)$

Approach:

1. Generate a Hypothesis (🔮)
2. Prove the Hypothesis for the Base Case
3. Prove the Hypothesis Inductively

#### Generate a Hypothesis

Approach: Write out the rule for increasing $n$

$\Theta(1)$, $2\Theta(1)$, $3\Theta(1)$, $4\Theta(1)$, $5\Theta(1)$, $6\Theta(1)$, $7\Theta(1)$, $\ldots$

What's the pattern?

Hypothesis: $T(n) \in O(n)$
(there is some $c > 0$ such that $T(n) \leq c \cdot n$)

#### Factorial

Let's make the constants explicit

$$T(n) = \begin{cases} c_0 & \textbf{if } n \leq 0\\ T(n-1) + c_1 & \textbf{otherwise} \end{cases}$$

Solve for $T(n)$

#### Prove the Hypothesis for the Base Case

$T(1) \leq c \cdot 1$

$T(1) \leq c$

$c_0 \leq c$

True for any $c \geq c_0$

#### Prove the Hypothesis for the Base Case+1

$T(2) \leq c \cdot 2$

$T(1) + c_1 \leq 2c$

$c_0 + c_1\leq 2c$

We know there's a $c \geq c_0$, so... $c_1 \leq c$

True for any $c \geq c_1$

#### Prove the Hypothesis for the Base Case+2

$T(3) \leq c \cdot 3$

$T(2) + c_1 \leq 3c$

We know there's a $c$ s.t. $T(2) \leq 2c$,
... so if we show that $2c + c_1 \leq 3c$, then $T(2) + c_1 \leq 2c + c_1 \leq 3c$

$c_1 \leq c$

True for any $c \geq c_1$

#### Prove the Hypothesis for the Base Case+3

$T(4) \leq c \cdot 4$

$T(3) + c_1 \leq 4c$

We know there's a $c$ s.t. $T(3) \leq 3c$,
...so if we show that $3c + c_1 \leq 4c$, then $T(3) + c_1 \leq 3c + c_1 \leq 4c$

$c_1 \leq c$

True for any $c \geq c_1$

Hey... this looks like a pattern!

#### Prove the Hypothesis Inductively

Approach: Assume the hypothesis is true for any $n' < n$;
use that to prove for $n$

#### Prove the Hypothesis Inductively

Assume: There is a $c > 0$ s.t. $T(n-1) \leq c\cdot (n-1)$

Prove: There is a $c > 0$ s.t. $T(n) \leq c\cdot n$

$T(n-1) + c_1 \leq c \cdot n$

By the inductive assumption, there is a $c$ s.t. $T(n-1) \leq (n-1)c$, so if we show that $(n-1)c + c_1 \leq nc$, then $T(n-1) + c_1 \leq (n-1)c + c_1 \leq nc$

$(n-1)c + c_1 - (n-1)c \leq nc - (n-1)c$

$c_1 \leq c$

True for any $c \geq c_1$

#### Factorial


def factorial(n: Int): Long =
if(n <= 1){ 1 }
else { n * factorial(n-1) }


How much space is used?

#### Tail Recursion


def factorial(n: Int): Long =
if(n <= 1){ 1 }
else { n * factorial(n-1) }


↳ the compiler can (sometimes) figure this out on its own ↴


def factorial(n: Int): Long =
{
var total = 1l
for(i <- 1 until n){ total *= i }
}


#### Tail Recursion

If the last action in the function is a recursive call, the compiler will turn it into a loop.

Scala: Add @tailrec to a function to get the compiler to yell at you if it can't convert the function.

Time permitting...

#### Fibonacci

What's the complexity? (in terms of n)


def fib(n: Int): Long =
if(n < 2){ 1 }
else { fib(n-1) + fib(n-2) }


#### Fibonacci

$$T(n) = \begin{cases} \Theta(1) & \textbf{if } n < 2\\ T(n-1) + T(n-2) + \Theta(1) & \textbf{otherwise} \end{cases}$$

Solve for $T(n)$

#### Next time...

Divide and Conquer

Recursion Trees