here is a sample program that he provided us for reference $//$ Function Prototypes

int fib$\_$iterative$($int n$)$;

int fib$\_$recursive$($int n$)$;

$//$ main Definition

int main$()$

$\{$

int n; $//$ Desired position of the fibonacci sequence.

cout $$ "Enter desired position of the Fibonacci sequence: $"$;

cin $>>$ n;

cout $$ endl $$ endl;

cout $$ "Calculating using the Iterative method: $"$ endl;

auto iStart $=$ high$\_$resolution$\_$clock::now$()$; $//$ Records the current time, storing it in iStart. auto specifies the type will be determined by initialization.

cout $$ "Position $"$ n calculated to be $"$ fib$\_$iterative$($n endl; $//$ Run the actual fib$\_$iterative$($n$)$ function.

auto iStop $=$ high$\_$resolution$\_$clock::now$()$; $//$ Records the time after the function has executed, storing the value in iStop.

$//$ The line below displays the time taken to run the function by counting the microseconds elapsed between iStop and iStart.

cout $$ "Value calculated in $"$ duration$\_$cast$($iStop $-$ iStart$).$count microseconds.";

cout $$ endl $$ endl;

cout $$ endl $$ endl;

cout $$ "Calculating using the Recursive method: $"$ endl;

auto rStart $=$ high$\_$resolution$\_$clock::now$()$; $//$ Same as above, but for the recursive function now.

cout $$ "Position $"$ n calculated to be $"$ fib$\_$recursive$($n endl;

auto rStop $=$ high$\_$resolution$\_$clock::now$()$;

cout $$ "Value calculated in $"$ duration$\_$cast$($rStop $-$ rStart$).$count microseconds.";

cout $$ endl $$ endl;

system$("$pause$")$;

return $0$;

$\}$

$//$ Other Definitions

int fib$\_$iterative$($int n$)$

$\{$

int currentVal $=0$;

int nextVal $=1$;

for $($int i $=0$; i $$ n; i$++)$

$\{$

currentVal $=$ currentVal $+$ nextVal;

nextVal $=$ currentVal $-$ nextVal;

$\}$

return currentVal;

$\}$

int fib$\_$recursive$($int n$)$

$\{$

if $($n $==0)//$ First base case test

return $0$;

else if $($n $==1)//$ Second base case test

return $1$;

else

$\{$

$//$ Recursively calculates the sum of the sequence values at n$-1$ and n$-2$

return fib$\_$recursive$($n $-1)+$ fib$\_$recursive$($n $-2)$;

$\}$

$\}$Recursive functions, or functions that call themselves, can be an alternative to loops to solve tasks that

can easily be broken down into smaller sub$-$problems of the original. In this lab, you will begin to

practice with writing and calling recursive functions.

EXAMPLE PROGRAM

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, we'll 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 $\frac{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,\frac{4}{2}=2,\frac{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.

When you are done, submit your completed $.$cpp file through the Blackboard submission tool. Please

name your file according to the usual convention, $[$Last Initial$][$First Name$]\_$Lab$3.$cpp$.$

Lab Output Screenshot Example: