For what n value (approximately) does your computer stop producing output? Why is this? Enter your answer in the 'Comments' field when you submit the file.

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 define itself. 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.

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.