CS1101S Studio S3 (T08C)

Recursion; Iterative and Recursive Processes

Question 1

Consider the following Source program:

function f1(rune_1, n, rune_2) {
    return n === 0
        ? rune_2
        : f1(rune_1, n - 1, beside(rune_1, stack(blank, rune_2)));
}

show(f1(square, 3, heart));

Use the substitution model on runes demonstrated during Lecture L2 in order to manually evaluate the expression f1(square, 3, heart). The evaluation proceeds as demonstrated in L2. For the primitive rune square, you should draw a solid box ⬛ and for the primitive rune blank, you should draw an empty box ⬜.

Of course as the computation proceeds according to the substitution model, the pictures within your expressions will become more complex. Try to get the proportions right and draw the pictures as large as necessary.

Question 2

Consider the following Source program:

function f2(rune, n) {
    return n === 0
        ? rune
        : stack(beside(blank, f2(rune, n - 1)), square);
}

show(f2(heart, 3));

Use the substitution model on runes demonstrated during Lecture L2 in order to manually evaluate the expression f2(heart, 3). The evaluation proceeds as demonstrated in L2. For the primitive rune square, you should draw a solid box ⬛ and for the primitive rune blank, you should draw an empty box ⬜.

Of course as the computation proceeds according to the substitution model, the pictures within your expressions will become more complex. Try to get the proportions right and draw the pictures as large as necessary.

In-Class Exercise

The goal of this in-class exercise is to write a function moony that takes a parameter n and produces a rune with n circles on the steps of a staircase.

Question 1

Begin by writing a function moony_1 that takes an argument bottom_right and produces a rune as shown in this picture.

The picture is the result of show(moony_1(ribbon)).

function moony_1(bottom_right) {
    return beside(stack(circle, square), stack(blank, bottom_right));
}

Question 2

Now that we have one circle, we need to produce n − 1 more. Use recursion in a function moony_2 to insert n − 1 other circles in the approximately correct location.

The picture is the result of show(moony_2(5)).

function moony_2(n) {
    return n === 1
        ? circle
        : moony_1(moony_2(n - 1)); 
}

Question 3

Use the available primitive combinations on runes to even out the rows and columns, one axis at a time. You may call your final version moony.

The picture on the left show the result of evening out the rows but not yet the columns, and the picture on the right shows the result of show(moony(5)).

function bottom_right(n, rune){
    return stack_frac(1 / n,
                      beside_frac(1 / n, circle, blank),
                      beside_frac(1 / n, square, rune));
}

function moony(n) {
    return n === 0
            ? circle
            : bottom_right(n, moony(n - 1));
}

Can you explain how your moony manages to even out both rows and columns?

Question 4

Do your solutions give rise to recursive or iterative processes?

Recursive

Characterize the resource consumption of your function moony using the orders of growth notation introduced in Brief B2.

In your description, be clear about what you consider the "size" of the given problem.

What assumptions are you making on the resource consumption of primitive runes and of primitive operations on runes? To answer this question, review question "Do all primitive operations considered to take the same time?" in the recording of Brief B2 (1:14:22).

Bonus Round

Question 1

Consider the following function:

function expt(b, n) {
    return n === 0 ? 1 : b * expt(b, n - 1);
}

Does power give rise to an iterative or recursive process?

Use the

$\mathrm{\Theta }$ notation to characterize the time and space consumption of expt as the argument n grows.

Use the

$\mathrm{\Theta }$ notation to characterize the time and space consumption of expt as the argument b grows.

Question 2

Consider the following relationship

$$b^n=\{\begin{array}{ll}{b}^{n/2}{b}^{n/2}& \text{if }n\text{ is even}\\ b^{(n-1)/2}{b}^{(n-1)/2}b& \text{if }n\text{ is odd}\end{array}$$

• Implement a function fast_expt which computes
  $b^n$ for any natural number
  $n$ in
  $\mathrm{\Theta }(\log (n))$ time

• How can you extend this to integer powers?

• Does your implemetation give rise to an iterative or recursive process?

• If iterative, can you write a version that gives rise to a recursive process? If recursive, can you write a version that gives rise to an iterative process?