The example program this week implements a recursive solution to calculate the values of the Fibonacci Sequence. It also calculates those same values iteratively, using only a loop, and displays information about the amount of time required to calculate each solution.

In the case of the Fibonacci sequence, well see from this program that recursion is not always the most efficient answer the extra overhead of managing all of those repeated function calls slows things down considerably as values increase.

YOUR PROGRAM

The Collatz Conjecture is a conjecture in mathematics that concerns a sequence sometimes known as hailstone numbers. Given any positive integer n, the following term, n+1 is calculated as follows:

If n is even, then n+1 is defined as n/2.

If n is odd, then n+1 is defined as 3n + 1

The Collatz Conjecture states that, for any value of n, the sequence will always reach 1. Once the pattern reaches 1, it repeats indefinitely (3 * 1 + 1 = 4, 4/2 = 2, 2/2 = 1)

For your lab, you will write a recursive function to calculate and display the sequence of hailstone numbers from any initial starting point, n, until it reaches 1. Additionally, after the sequence terminates at 1, you should print out the number of steps that were required to reach that point.

Notes:

The Collatz Conjecture is unproven, but works for every case ever tested. For the purpose of this lab, we will assume it works in all cases, so you can rely on the sequence always reaching 1.

Counting the number of recursions required can be handled in a number of different ways, including additional parameters to the function or a static local variable. The choice is yours.

c++