CS1101S Studio S4 (T08C)

Tree Recursion

The following pattern of numbers is called Pascal's triangle.

$$\begin{gathered} 1 \\ 11 \\ 121 \\ 1331 \\ 14641 \end{gathered}$$

The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it.

Question 1

Write a function pascal that computes elements of Pascal's triangle by means of a recursive process, i.e. the function should take two arguments, row (counted from the top, starting with 1), and position (counted from the left, starting with 1), and return the element for the specified row and position. Note that only one element must be returned and NOT the
entire row. E.g. calling the method with row = 3 and position = 2 should return 2. Likewise calling the method with row = 5 and position = 3 should return 6.

function pascal(row, position) {
    return position === 1 || position === row
        ? 1
        : pascal(row - 1, position - 1)
            + pascal(row - 1, position);
}

Question 2

Similar to the tree for fib(5) in section 1.2.2 and the tree for cc(11, 5) in the solution for exercise 1.14, draw the tree illustrating the process generated by pascal(5, 4) to compute the value in Pascal's triangle in row 5 and position 4. Does your function pascal give rise to a recursive or an iterative process?

Higher-order Functions

Question 1

Consider compose(math_sqrt, math_log), which is a function of type Number-Transformation. What is the result of compose(math_sqrt, math_log)(math_E)?

1

What is the result of compose(math_log, math_sqrt)(math_E * math_E)?

1

Question 2

As we have used it above, the function compose takes as arguments two functions of type Number-Transformation, and returns another such function. We indicate this with the notation:

$$\mathtt{\text{compose}}:(Number-Transformation,Number-Transformation)\to Number-Transformation$$

Just as squaring a number multiplies the number by itself, applying thrice to a function composes the function three times. That is, (thrice(f))(n) will return the same number as f(f(f(n))):

function thrice(f) {
    return compose(compose(f, f), f);
}

What is the result of evaluating thrice(math_sqrt)(256);?

2

Question 3

Implement thrice using repeated.

function thrice(f) {
    return repeated(f, 3);
}

What is the result of the following program?

thrice(thrice)(x => x + 1)(0);

27

Question 4

See if you can now predict what will happen when the following statements are evaluated. Briefly explain what goes on in each case.

((thrice(thrice))(add1))(6);

33

((thrice(thrice))(x => x))(compose);

compose

((thrice(thrice))(square))(1);

1

((thrice(thrice))(square))(2)

2^(2^27)