dg4.md

Discussion Group Exercises Week 4

Problems

Problem 1

What is the recursive definition of Pascal's triangle? What are the base cases?

1. row == 1
2. column == 1 (first element of each row)
3. column == row(last element of each row)

function pascal_triangle(row, column) {
    if (row === 1 || column === 1 || column === row) {
        return 1;
    } else {
        return pascal_triangle(row - 1, column - 1) + pascal_triangle(row - 1, column);
    }
}
// test, working
pascal_triangle(3, 2);  // should return 2
pascal_triangle(5, 3);  // should return 6

Problem 2

Draw the recursion tree of the cc (count-change function) to make change for 11 cents, using 50,20,10,5, and 1 cents.

Problem 3

• function that computes $f$ by a recusrive process
• function that computes $f$ by an iterative process $$ f(n) = \begin{cases} f(n-1)+2f(n-2)+3f(n-3), & \text{if }n < 3 \ n, & \text{if }n < 3 \end{cases} $$ Solution:

// recursive procedure
function f(n) {
    return n < 3 ? n : f(n-1) + 2*f(n-2) + 3*f(n-3);
}
 
// iterative procedure
function f(n) {
    function _f(n_1, n_2, n_3, i) {
        if (i === n) {
            return n_1 + 2 * n_2 + 3 * n_3;
        } else {
            return _f(n_1 + 2 * n_2 + 3 * n_3, n_1, n_2, i + 1);
        }
    }
    return n < 3 ? n : _f(2, 1, 0, 3);
}
// confirmed working

Problem 4

function f(g) {
    return g(4);
}
f(Math.sqrt);    // 2
f(function(z) { return z * (z + 1); }); // 20

What happens if we (oddly) ask the interpreter to evaluate the combination f(f);? Explain. Infinite loop

Problem 5

a) ((thrice(thrice)))(add1))(6) = 33 b) ((thrice(thrice))(identity))(compose) = compose c) ((thrice(thrice))(square))(1) = 1 d) ((thrice(thrice))(square))(2) = 2 ** 27