---
# System prepended metadata

title: In Class Studio 3

---

# In Class Studio 3
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. The picture below is produced by
`show(moony(5))`.
## Problems

### Question 1.
1. Begin by writing a function moony_1 that takes an argument bottom_right and produces a rune as shown in this picture.
![](https://i.imgur.com/CmS6UmY.png)
The picture is the result of ```show(moony_1(ribbon))```

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

### Question 2.
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.
![](https://i.imgur.com/P6DuCD7.png)
The picture is the result of show(moony_2(5)).

```javascript=
function moony_2(n){
    return n === 0
    ? circle
    : stack(beside(circle, blank),             beside(square, moony_2(n - 1)));
}

show(moony_2(5));
```

### Question 3.
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.
![](https://i.imgur.com/Jk1B6U8.png)
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))`.
Can you explain how your moony manages to even out both rows and columns?

```javascript=
function moony(m){
    return m === 1
           ? circle
           : beside_frac(1/m,moony(m-1), moony_2(circle,m));
}

function moony(n){
    return n === 1
    ? circle
    : stack_frac(1 / n, beside_frac(1 / n, circle ,blank), 
        beside_frac(1 / n, square, moony(n - 1)));
}

show(moony(5));
```

### Question 4.
4. Do your solutions give rise to recursive or iterative processes? 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).

// It is a recursive problem as there is an accumulation of deffered operations
// Order of growth -> O(n)
// Size -> number of deffered operations
// Assumptions - all primitive functions take up constant space and time

// YOUR SOLUTION HERE

### EXTRA Question 1.
// Expt gives rise to a recursive process (deferred operations are accumulated).
// Theta(n) as n grows.
// Theta(1) as b grows.

### EXTRA Question 2.
// YOUR SOLUTION HERE

function fast_expt(b, n) {
    return n % 2 === 0 || n === 0 
    ? fast_expt(math_pow(math_pow(b, n / 2), 2), n - 1) 
    : fast_expt(b * math_pow(b, n - 1), n - 1); 
}

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