
5.4.2.6 Example: the Collatz problem Since the previous example may have left the reader with an impression that NestWhile is only good to produce inefficient solutions, we will now consider an example where it is perhaps the most appropriate command to use, both in the sense of elegance and efficiency. The Collatz iteration is given by:
It has been noticed that, regardless of the starting number <n>, the sequence of numbers that result from the repeated application of the function <c> will always eventually go to 1 (although this has not been rigorously proven). The most interesting question is how the length of the Collatz sequence depends on the starting number.
Look carefully at this implementation. The idea behind is beautiful: we recursively define the sequence by prepending a starting number to the sequence which starts with the transformed starting number. The separate base case guarantees a proper termination of the recursion. For example:
Let us test the performance of this solution (I chose the powers of 2 since then the length of the Collatz sequence is known in advance and is equal to the power of 2)
We had to temporarily disable a limit on number of recursive calls (recursion depth) since we will need the depth of recursion equal to the power of 2, in each case. The standard limit is 256. <Block> is used to make this modification local to its interior. We use <Block> when we want some function or expression to temporarily "forget" the associated external (global) rules. Here is an alternative implementation using NestWhileList:
Check:
We now test the performance :
This version does not communicate the idea and recursive nature of the Collatz sequence so clearly (which was probably the main motivation of Maeder. Besides, NestWhileList did not exist at the time), but the performance of this version is much better. This is because, the sequence (list) is created internally inside NestWhileList, and we don't have to modify large lists in place. The complexity of this program depends on details of internal implementation of NestWhileList, but could be even linear or loglinear, if c[x] is approximately constanttime (or log). We see that this problem is tailormade for NestWhileList. It can be also seen by the conciseness of the code. Note that should we have only NestWhile at our disposal, this solution would not be possible  in this case we needed exactly NestWhileList.

