--- tags: cs1101s --- # CS1101S Studio S4 (T08C) ## Tree Recursion The following pattern of numbers is called Pascal's triangle. $$ 1 \\ 1 \qquad 1 \\ 1 \qquad 2 \qquad 1 \\ 1 \qquad 3 \qquad 3 \qquad 1 \\ 1 \qquad 4 \qquad 6 \qquad 4 \qquad 1 $$ 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`. ```javascript! 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: $$ \texttt{compose} : (Number-Transformation, Number-Transformation) \rightarrow 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)))`: ```javascript! 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`. ```javascript! function thrice(f) { return repeated(f, 3); } ``` What is the result of the following program? ```javascript! 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. ```javascript! ((thrice(thrice))(add1))(6); ``` ```! 33 ``` ```javascript! ((thrice(thrice))(x => x))(compose); ``` ```! compose ``` ```javascript! ((thrice(thrice))(square))(1); ``` ```! 1 ``` ```javascript! ((thrice(thrice))(square))(2) ``` ```! 2^(2^27) ```