So far in our study of recursion, we identified a few common recursive number sequences, such as the Fibonacci numbers. Number sequences like this are not recursive algorithms themselves -- their definitions are ways of generating the "nth term", rather than ways of breaking down a larger problem -- but they can serve as good examples of the practical limits of recursion.

Some sequences are notoriously hard to compute (with recursion, at least) because of the deep layers required, as we will see in this week's lab.

Golomb's sequence is known as "self-describing" -- it seems to know about its own future terms. It is defined as the sequence of natural numbers such that n appears exactly G(n) times in the sequence. Here are the first few values of G(n) for some n:

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
G(n)	1	2	2	3	3	4	4	4	5	5	5	6	6	6	6

The sequence starts at 1, with G(1) = 1.

It's not too hard if you step through it one term at a time.

For n = 1, G(n) is 1. If you look at the sequence (the entire sequence G(n) all the way to infinity -- it seems to "know" about itself), 1 appears only 1 time.

For n = 2, G(n) is 2. Looking again at the G(n) sequence, the number 2 appears 2 times. But it's looking into the future! The next value of '2' isn't until G(3).

For n = 3, G(n) is 2. You can see that 3 appears 2 times.

For n = 4, G(n) is 3. ... and 4 appears 3 times.

And so on and so forth.

The formula is:

G(n) = 1 + G(n - G(G(n - 1)))

Assignment

Write a C++ program that recursively computes the terms of G(n) in a loop, as follows:

• Loop from 1 to a maximum value of your choice, computing G(n) for each. In each loop iteration, the program should output:
  • n (starting at 1, 2, 3, ...)
  • The calculated value G(n)
  • A count of how many times G() was called for that value of n. You can code this any way you choose.
• Format the output the same way as in the example below.
• The program does not need to accept any input, but you will need to make the loop sufficiently long so you can determine your answer for the second part below -- you may need to experiment with different values.
• Remember to think about the base case.

If implemented correctly, your program will run for a short while and then slow to a crawl. Eventually, it will stop producing output but will still be running.

Example Output

The output of your program should look exactly like this, except that there will be more lines. This is an example of looping through n == 15:

G(1) = 1, called 1 times G(2) = 2, called 4 times G(3) = 2, called 10 times G(4) = 3, called 19 times G(5) = 3, called 40 times GC6) = 4, called 70 times G(7) = 4, called 109 times G(8) = 4, called 169 times G(9) = 5, called 259 times G(10) = 5, called 409 times G(11) = 5, called 619 times G(12) = 6, called 919 times G(13) = 6, called 1249 times G(14) = 6, called 1729 times G(15) = 6, called 2419 times