Comp 210 Lab 7: Generative recursion, Homework hints

A Funny Function, Finding a root of a function, Homework hints


A Funny Function

Consider the function

f(n) =  { n/2    if n is even,
        { 3n+1   otherwise
While it may look like a pretty mundane function, try iterating it (repeating it over and over, using the previous result), and seeing how long it takes to reach 1 (if ever). (This is known as Colatz's (?) function.)

An example: if we start with (say) 5, we find that:

So starting with an initial value of 5, iterating f leads to 1 in five steps. "Sure," you say, "that starting point of 5 happens to lead to 1 after a few steps, just lucky!" What if we start iterating from 3? From 17?

Write a program stops? which take a number n, and return #t if n, f(n), f(f(n)), ..., ever reaches the number 1. (What does your program do if this doesn't happen?) This function is an example of generative recursion: the answer to (stops? n) might depending generating a new instance, 3n+1, and recursing on that. Notice that unlike structural recursion, there is no guarantee that our generative-recursion problem is going to finish.

Why do we choose to stop at f(1)?

Now, write a modified function time-til-stop (or tts if you hate typing), which instead of returning #t, it returns the number of steps until 1 is reached. That is, (time-til-stop 5) = 5.

(This function can be written without using an accumulator. If you wanted, you could also use an accumulator for it. Really, you should have enough knowledge to write it either way.)

Test time-til-stop on some large numbers, say 1001 and 2349872349247991. (Put these test in your program window, so you don't need to keep re-typing them as we modify time-til-stop.)


Finding a root of a function

As a different example of generative recursion, consider using Newton's Method to find a root of a function--that is, where the graph crosses the x-axis.

Newton's method will be described by the TA on the board. Roughly, you start with an initial guess x0 as to where a function f crosses the x-axis. The guess is probably wrong, so generate a next guess by the following method:

  1. Calculate the slope of the function f at x0.
  2. Extend the tangent line from (x0,f(x0)) and see where that line crosses the x-axis.
  3. Use that line-crossing as an estimate as to where the complicated function f crosses the line, making that new point x1.
  4. Repeat this process using x1, x2, etc., until your solution is "close enough".
A picture is worth a thousand words (but don't worry about all the words on that link unless you want to).

Newton's method often converges very quickly to a root, but you can also think of cases where it is foiled: it might divide by 0, it might loop or diverge, and even if it gives you a root, it might not be the root you want.

A hint and test data are available.


Homework hints

In lab, we will discuss some ideas about what states are for the Missionaries & Cannibals problem. The following are some generalities to consider:

  1. The first step is to think about is what pieces of information are important to know. For this problem, what do we need to know about the missionaries, cannibals, boat, and sides of the river?
  2. The second step is to choose how to represent that data.

Your M&C program needs to build up a list of moves to the result. That sounds similar to our in-class example that built up a list of cities visited in a path.