---
tags: Matlab Workshop
---

# Lesson 5: Recursion, Dynamic Programming

## 1. Recursion
Recursion (遞迴) occurs when the definition of a concept or process depends on a simpler or previous version of itself [wikipedia-recursion](https://en.wikipedia.org/wiki/Recursion).

:::info
Factorial is defined as

n! = 1 x 2 x ... x (n-1) x n

Or, we could use a recursive definition

factorial(n) = n * factorial(n-1)

:::

We can use functions to define a recursion. The function would call itself within its definition.

function result = factorial(n)
   if n <= 1
       result = 1;
   else
       result = n * factorial(n-1);
   end
end
disp(factorial(5)) % 120

### Fibonacci sequence
1, 1, 2, 3, 5, 8, 13, 21, ...

`n` is the length of the sequence. `i` is the index of the sequence element.
- `i` $\in\{1, 2\}$ $\rightarrow$ `Fibonacci(i)` $= 1$
- `i` $>2$ $\rightarrow$ `Fibonacci(i)` $=$ `Fibonacci(i-1)` $+$ `Fibonacci(i-2)`

:::warning
Please implement the above calculation.

function result = fibonacci(i)
    if ...
      % some equation you want to put
    else
        % equation for getting the fibonacci sequence
    end
end
disp(fibonacci(8)) % >>> 21
disp(fibonacci(21)) % >>> 10946

Put your code [here](https://hackmd.io/k4ni6ad7TRKt85VCPVQmeg).
:::

## 2. Dynamic programming (DP)

In the previous example when calculating Fibonacci sequence, we can break down the overall recursion steps. For example when calculating fib(5),


We can see a lot of repeated work is done.

Three points of dynamic programming:
1. **Avoiding redundant calculations**
We use the recursion idea.
2. **Bottom-up approach**
Starting from a simple case (`fib(0)`) up to complex cases (`fib(N)`)
3. **Memorization**
Recording the previous answers instead of calculate them everytime. We can store previous ```fib(n)``` results.

function r = memo_fib(n)
    % Handle base cases directly
    if n == 1 || n == 2
        r = 1;
        return;
    end
    
    % Initialize memo array for iterative approach
    memo = zeros(1, n);
    memo(1) = 1;
    memo(2) = 1;
    
    % Fill the memo array iteratively
    for i = 3:n
        memo(i) = memo(i-1) + memo(i-2);
    end
    
    % Result is the nth Fibonacci number
    r = memo(n);
end

disp(memo_fib(8)) % 120
disp(memo_fib(21)) % 720

"Memorization" and "Dynamic Programming" are often used interchangeably.

Now, let's see the execution speed of both recursion and dynamic programming.

:::info
### Let's try! Why one runs faster?

Using the fibonacci example using recursion:
tic; disp(fibonacci(30)); toc 


Using the fibonacci example using dynamic programming
tic; disp(memo_fib(30)); toc 

`tic` and `toc` are functions to check the execution speed of the code.
:::

### Sample Outline for Homework 1

%input
input sequence 1 (dealing with characters)
input sequence 2 (dealing with characters)

%scores
match_score (dealing with integer)
mismatch_penalty (dealing with integer)
gap_penalty (dealing with integer)

%creating the initial matrix with zeroes as values
%use the sequence length as the row (sequence 2) and column (sequence 1)

matrix dimension(seq_1_length, seq_2_length)
Hint: using the function: zeros(n,m)

%fill in the initial matrix with scores
%calculate for the match or mismatch score for each base 

for i = 1:seq_2_length+1
    for j = 1:seq_1_length+1
        %checking the top, left, and diagonal cells
        %get the max score among these three
    end
end


%Traceback part
1.You need to store aligned sequences

2.You need to start from the very bottom cell which is (sequence_1_length, sequence_2_length)

3.Evaluate the scores to know the direction of tracing back
Hint:
    a) Use while loop to have loop until you go back to the leftmost cell
    b) Use if-else condition to know whether to put a gap or proceed to the next nucleotide
    
4.Reverse the aligned sequence you stored from the end of the sequence or bottom-most right cell of the score matrix

## Knapsack problems

### 0-1 knapsack problem

Now, we look at the 0-1 knapscak problem. "0-1" means that an item can be either taken or not taken (no available item). We can solve the problem using the naive searching approach (brute force approach), but it would get very slow when there is a lot of items.

Goal: To find the number of items that will give us the highest price given a maximum capacity (weights) you can buy.

Combination count:

2 ^ #items

We can use DP on this problem.

values = [6, 4, 10, 12];
weights = [1, 4, 2, 3];
capacity = 5;

We construct a 2D array of [N_items][capacity]

| | cap: 0 | cap: 1 | cap: 2 | cap: 3 | cap: 4 | cap: 5 |
|---|---|---|---|---|---|---|
| # of item available: 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| # of item available: 1 | 0 | | | | | |
| # of item available: 2 | 0 | | | | | |
| # of item available: 3 | 0 | | | | | |
| # of item available: 4 | 0 | | | | | |

x: capacity
y: item count
val: highest price

prices = [6, 4, 10, 12];
weights = [1, 4, 2, 3];
capacity = 5;

n = length(prices);
table = zeros(n+1, capacity+1);

for i = 1:n+1
    for j = 1:capacity+1
        if i==1 || j==1 % boundary condition
            table(i, j) = 0;
        else                       
            new_item_idx = i-1;
            cap_limit = j-1;
            new_item_weight = weights(new_item_idx);
            new_item_price = prices(new_item_idx);

            if new_item_weight <= cap_limit
                % we could either take it or not take it
                take_price = new_item_price + table(i-1, j-new_item_weight);
                not_take_price = table(i-1, j); % as if this item is not available
                table(i, j) = max(take_price, not_take_price);
                
            else % this item is too heavy, as if this item is not avialable
               table(i, j) = table(i-1, j); 
            end
        end
    end
end

:::info
### Exercise

We have a rod of length n and rods with different length have different price. We want find the optimal way to cut the rod to obtain the highest profit.


Hint:

When n = 1, optimal profit is 1, we say f(1) = prices[1]

When n = 2, we can choose to cut or not cut, so the optimal profit is max(f(1)+prices[1], prices[2])

When n = 3, optimal profit would be max(f(2)+prices[1], f(1)+prices[2], prices[3])

prices = [1, 5, 8, 9, 10, 17, 17, 20];
optimal_profits = zeros(1, 8);

a = length(prices)
for i = 1:a
    if i == 1 % boundary condition
        optimal_profits(i) = prices(1);
    else
        % recursive definition here!
        
    end
end

:::

## Take Home Exercise

### 1. 2D Maze

There's a 2D maze with some rocks on the way and you cannot walk across rocks. Calculate how many different but meaningful routes a person can take from the starting point to the ending point.