# Computation

Recursion is also very useful technique in computation. It can be used for many optimizatoin tasks, combinatoric tasks, probability tasks in games and much more. It can explore the best move in some open two player game like chess, go, checkers, 5 in row. For some problem does not suits good. Sometimes is recursive solution best in performance. There are some set of problems where Dynamic Programming turns very bad solution in very efficient one.

# Dynamic Programming

There are more types of dynamic programming.

One is bottom-up where we are filling table usually by using for cycles.
Second is top-down DP (co called memorization tichnique), where we have recursion and we are memorizing results.

Bottom up solution is a bit more efficient, but it is harder to figure out. We will stick with memorization technique, since it is more related to recursion.

Memorization technique is useful when in our recursion problem there are sub calls that repeats.

For instance fibonacci function.

long fibonacci(int num) {
    if (num <= 0) return 0;
    if (num == 1) return 1;
    return fibonacci(num-1) + fibonacci(num-2);
}

int main() {
    for (int i = 0; i < 100; i++) {
        printf("%3d: %ld\n", i, fibonacci(i));
    }
}

It generates uncomplete binary three of depth n. Number of calls T(n) for input n is between 2^(n/2) <= T(n) <= 2^n it is O(2^n). This crazy sufficient complexity is because of repetitices calls. If we would compute each call just once, and store result. Then we do not need to compute result for same input again.

long cache[100]; // it owerflows much earlier
long fibonacci(int num) {
    if (num <= 0) return 0;
    if (num == 1) return 1;
    // if we have answer in the table we can just use it.
    if (cache[num] != 0) return cache[num];
    // we will cache every answer
 
    return cache[num] = fibonacci(num-1) + fibonacci(num-2);
}

int main() {
    for (int i = 0; i < 100; i++) {
        printf("%3d: %ld\n", i, fibonacci(i));
    }
}

# GDC - Greated Common Divisor

Also known as Euclidean algorithm.

reveal solution

long gcd(long a, long b) { 
    return b == 0? a : gcd(b, a % b);
}

TIP

This algorithm performes very well.

# Combination Numbers

Use rule from Pascal triangle. comb(n, k) = comb(n-1, k-1) + comb(n-1, k)

reveal solution

#include <stdio.h>

long comb(long n, long k) {
    if (k == 0) return 1;
    if (k < 0 || k > n) return 0;
    return comb(n-1, k-1) + comb(n-1, k);
}

int main () {
    comb(32, 20); // few seconds withou DP
}

WARNING

This algorithm performes slowly, but can be optimized by Dynamic Programming.

# Dynamic programming

Improve previous algorithm to be very fast by using DP. Note that function grows very fast, when n is 100 it overflows long. There is no point to making bigger cache table.

reveal solution

// Global variable is not genius SW design, but it will do.
long dp[100][100]; // Globals are initialized by zeroes
// Cleaner solution is to pass array through parameter.

long comb(long n, long k) {
    if (k == 0) return 1;
    if (k < 0 || k > n) return 0;
    // when in cache table is non-zero, we already computed the value and we can use it.
    if (dp[n][k] != 0) return dp[n][k];

    // otherwise we compute and store into cashe table.
    return dp[n][k] = comb(n-1, k-1) + comb(n-1, k);
}

# Task Vines

to be solve

There are 1 <= N <= 1000 wines on the shelf, each wine has initial value V[i], where 0<=i<N. We have these wines for N years. Each year we will drink one wine on ceremony. We can grab from one end of the shelf, so just last or first, not from the middle. Value of wine grows over time. Starting first year 1 upto last year N. Value of wine is Y*V[i], where Y is year and V[i] is initial value of wine on index i. Task is to compute maximal possible value.

We may discuss greedy algorithm, does it work here?

6
3 2 5 1 1 4

Greedy (we just pick smaller number)

1*3+2*2+3*4+4*1+5*1+6*5
= 3  +4+12 +4  +5   +30
= 58

but better is

1*4+2*1+3*1+4*3+5*2+6*5
= 4+2  +3  +12 +10 +30
= 61

Lets implement brute force recursion so called backtrack function. Just try all combinations. Two recursive steps - we can pick from a left, we can pick from the right. Return result through return statement.

DETAILS

Simple, but this is bad prepared for DP. We would like have indexes instead of moving array pointer. Would like later use indexes as index into cache table.

// This innocent simple function does algorithm nicer
long max(long a, long b) {
    if (a > b) return a;
    return b;
}

// This is undesirable variant for DP, but we made it on purpose.
int wineRec1(int * wines, int n, int step, int accum) {
    // shelf is empty
    if (n < 1) return accum;
    // we count case of taking from right and case of taking from left
    // and return maximum profit
    int a = wineRec1(wines+1, n-1, step+1,accum + wines[0]*step);
    int b = wineRec1(wines, n-1, step+1,accum + wines[n-1]*step);
    return max(a, b);  
}

# Optimize with Dynamic Programming

show hint to prepare function

For dyamic programming we have to prepare our function to it. Lets separate parameters into groups. Parameters which are always same during recursion, it can be array wines and N. Parameters which consist together input combination, so that for same combination it is always same result. We would like to use these parameters as indexes into array. Accumulator is just hleper variable which allows as to cumulate midresults. Like before it is something undeserable for DP. We can accumulate result in return instead.

int wineRec2(int * wines, int begin, int end, int step) {
    if (begin > end) return 0;
    int a = wineRec2(wines, begin+1, end, step+1) + wines[begin]*step;
    int b = wineRec2(wines, begin, end-1, step+1) + wines[end]*step;
    return max(a, b);  
}

This is already ready for DP. We can do O(N^3) solution. If we can reduce parameters for input computation, we should do it. We have begin, end and step. All between 0 and 1000. It would be 1000^3 integers which is 4GB of memory. Seems to be quite a lot.

We can prepare function even further. We can pass n which does not change during call. Then we can deduce step from other variables.

int wineRec3(int * wines, int n, int begin, int end, int accum) {
    int step = n - (end - begin); // step can be deduced
    if (begin > end) return accum;
    int a = wineRec3(wines, n, begin+1, end, accum + wines[begin]*step);
    int b = wineRec3(wines, n, begin, end-1, accum + wines[end]*step);
    return max(a, b);  
}

This is nicely prepared for DP. Input configuration consists just from begin and end. All between 0 and 1000. It seems we could not do more. We need only 4MB on cache table and algorithm would be much quicker O(N^2).

reveal solution

int cache[1000][1000];

int wineRec4(int * wines, int n, int begin, int end) {
    int step = n - (end - begin);
    if (begin > end) return 0;
    // when we already have result we just use.
    if (cache[begin][end] != 0) return cache[begin][end];
    int a = wineRec4(wines, n, begin+1, end) + wines[begin]*step;
    int b = wineRec4(wines, n, begin, end-1) + wines[end]*step;
    // cashe result before return
    return cache[begin][end] = max(a, b);  
}

By this step we has transformed O(2^N) algorithm to O(N^2) algorithm.

← Generation Recursion