Note: Sadly, there’s no advanced tutorial today. We’ll resume working on our interpreter next week! If you have an idea that you’d like to explore more in either interpreting or functional programming, come find me and I can give you some things to investigate!

Submitting

Regardless of how you choose to complete the assignment, you MUST submit the file you worked on to Canvas.

If you’re submitting remotely, your submitted file will be graded for completeness and correctness via an autograder. Make sure your functions are named correctly and that all of the built-in check-expects pass.

If you’re submitting in-class, make sure to check-in (there will be one question called CHECK-IN Q only available for the first 7 minutes of class) and check-out (there will be a three questions survey called CHECKOUT SURVEY only available for the last 10 minutes of class) using PollEverywhere with your location verified.

Getting Started

Today we’ll continue to practice recursion with a specific focus on a specific type of recursion we call iterative recursion.

Like last time, there are no template files for this Tutorial so you’ll need to start from a blank DrRacket file. Keep in mind you’ll still need the language selector line at the top of your new file (#lang htdp/isl+).

After you’ve got a blank document open, might as well save it with a good sensible name somewhere on your computer where you store important docs.

Part 1. power

Write a function, power, that raises a number to a power: (power a b) should return a^b. So (power 4 2) is 4^2 = 16, (power 4 3) is 4^3 = 64, …, etc. Remember that in math class, for any a, (power a 0) is 1 (anything to the zeroth power is 1) and (power a 1) is a. We won’t worry about fractional or negative powers.

Time for our subgoals!

What is the type of power (that is, what is its type signature, the types of its input and output)?

Step 1. What is the purpose statement for it?

Step 2. What should the base case be (aka the “easy case”) for the recursion? Note that here we have two inputs to the function. Which one would we be changing as we recurse? Or would we change both of them?

Step 3. Use the usual template for the base case:

(if test-for-base-case
    answer-for-base-case
    TODO)

Where test-for-base-case is something that looks at the input to the function and determines if it’s the base case input and answer-for-base-case is the answer for the base case. We’ll fill in TODO in a minute.

Step 4. What’s the recursive case? Remember the recursive case is what runs when the input is too hard to be handled by the base case. We call ourselves on a version of the input that’s one step closer to being the base case. Then we take the answer to that and turn it into the answer for the original problem. So you can to decide two things:

Step 5. Now fill in the part in your code that says TODO:

Part 2. power/iter

Now write power as an iterative recursion. Start by writing a helper function, power-helper, that takes an extra accumulator input:

(define (power-helper number exponent accumulator)
   ...stuff...)

Note: Function definition look weird? Checkout the section on Sussman form from Tutorial 4!

And returns the answer (number raised to exponent). To do that, first answer these questions for yourself:

And finally, write the definition of power itself:

(define power/iter
  (lambda (number exponent)
   (power-helper ...fill this in...)))

Having trouble? See if this walkthrough step-by-step helps.

Interlude - cond

So sometimes you want to do conditionals that have more than two branches. For instance, “if the number i’m looking at is 6, then do this, otherwise if it’s 5 then do this, if it’s 4 then do this, etc.”.

You can totally do that by chaining if statements together…but it gets cumbersome pretty quickly. When you find yourself in that sort of situation, it’s better to use cond. cond is another special form that allows us to test multiple conditions and then do actions based on those tests.

When you just want to see if a test returns true or false and do two different actions, if and cond behave exactly the same. They just use different notation:

(if test
    do-this-if-test-true
    do-this-if-test-false)

is the same as this:

(cond [test do-this-if-test-true]
      [else do-this-if-test-false])

Notice there are a couple special parts of cond’s notation. The first is that you have to put square brackets before and after each test - action pair. The second is that we put else as the “test” for the last branch. You can think of else as a function that returns true only if all the previous tests return false.

Like I said, you don’t need cond for anything yet. But it is very useful for lots of branches in a program:

(cond [test do-this-if-test-true]
      [test-2 otherwise-do-this-if-test-2-true]
      [test-3 otherwise-do-this-if-test-3-true]
      [else otherwise-just-do-this])

See if you can use cond (with 2 branches) instead of using ifs for the next couple of problems!

Part 3. count/iter

Now write the count function from last time (with a new name):

count/iter: (X -> Boolean) (listof X) -> number

As an iterative recursion. Again, start by writing the helper function that returns the answer (the number of elements of list that satisfy the predicate).

(define count-helper
  (lambda (predicate list accumulator)
  ...stuff...))

To do that:

And finally, write the definition of count/iter itself.

Part 4. any?

Write a function, (any? predicate list) that returns true if predicate returns true for any element of list, otherwise it returns false.

Note: Yes, this is the same as ormap, we’re just naming it any? because ormap is already in use and also because ormap does not really make sense to someone that isn’t already thinking boolean-ly.

Note that you may write this as an iterative or non-iterative recursion. However, be aware that the iterative version doesn’t need an extra accumulator variable. You can write it with just two arguments, without needing to do a fixup step to the answer from the recursive call.

Note: Think about why this might be the case. Once you find one element that satisfies your predicate do you really care if the rest do?

We recommend just writing it and then looking at the result to see whether you ended up with an iterative or non-iterative version.

Part 5. every?

Write a function, (every? predicate list) that returns true if predicate returns true for every element of list, otherwise it returns false.

Note: Yep, you guessed it…it’s andmap! Think carefully about how this is different from Problem 4. Once you find one element that does not satisfy your predicate, do you really care if the rest do or do not?

You can write this as an iterative or non-iterative recursion.