Java
TOPIC 33 – RECURSION
AP EXTRA

AP LESSON WORK

QUESTION 1

Consider the non-recursive Fibonacci function below.

a) Copy and paste it to your class with your Fibonacci function from question 1. Test it with large numbers such as 45.

b) Is it faster or slower than the recursive function that we implemented together in class?

c) Give a disadvantage of having to write such code.

public static int fibNonRec(int n)

{

if (n == 1 || n == 2)

{

return 1;

}

else

{

int down2 = 1;

int down1 = 1;

int current = down1 + down2;

for(int x = 3; x < n; x++)

{

int tmpCur = current;

int tmpDown1 = down1;

current = current + down1;

down1 = tmpCur;

down2 = tmpDown1;

}

return current;

}

}

QUESTION 2

Research and implement the famous recursive function named the Ackerman function. What is its value when both parameters are 3?

QUESTION 3

The Collatz Problem is a famous problem in mathematics that sees you create a sequence that comes from an arbitrary first term t₁ (positive integer). The growth of the sequence follows:

if t_n equals 1, then sequence is done

if t_n is odd, t_n+1 = 3n + 1

if t_n is even, t_n+1 = t_n / 2

So, we start with 6, we get the following:

6, 3, 10, 5, 16, 8, 4, 2, 1

Or, if we start with 9, we get:

9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

The Collatz Problem states that the sequence will always end in a value of 1.

Implement this recursive function. Before anything else, you should output to screen the value of the current term. This way, once the program is done running, you should have a full listing of the sequence.

Also, when testing your function, you should ask the user for the first term of the sequence.