Programming Simple Recursive Problems

1.        Can the base case also have a recursive call in it? Explain why or why not.

2.        Which control statement (if, loop, case, etc) is always in a recursive function?

3.        Write an iterative version of the Fibonnaci function.

4.        Trace the recursive calls made when Fibonnaci (6) is called.

5.        What characteristics does a problem need to be able to be solved recursively?

6.        What can you say about a recursive program that has the following form?

If (Condition) then Perform Recursive Step

7.        Recall the code for the fibonnaci sequence:

public static int fib(int n)

//n is the term in the fib sequence we want, it is greater than 0

//the value of the term is returned

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

    return 1;

  else

    return fib(n-1)+fib(n-2)

}

Write code for the following sequences. You will use the following function heading for each:

public static int seq(int n)

//n is the term in the sequence we want, it is greater than 0

//the value of the term is returned

(a)     3, 5, 7, 9, 11… In this case, seq(4) = 9

(b)     1, 2, 4, 8, 16, 32 … In this case, seq(3) =4

(c)     1, 2, 2, 4, 8, 32 … In this case seq(5) = 8

(d)     2, 5, 7, 12, 19 … In this case seq(4) = 12

8.        The Forever Green Nursery owns 7000 white pine trees. Each year the nursery plans to sell 12% of its trees and plant 600 new ones.

(a)     Write the recursive program to model the Forever Green Nursery.

(b)     Use your program to determine the number of pine trees owned by the nursery after 10 years.

Rework the problem again, but this time your program should build in a catastrophe of some sort to the nursery in the 5^th year.

9.        A very old Arab legend, recounted by al-Yaqubi in the ninth century, begins, "It is related by wise men of India that when Husiya, the daughter of Balhait, was queen…" and goes on to tell how the game of chess was invented. The queen was so delighted with the game that she told the inventor, "Ask what you will." The inventor asked for one grain of wheat on the first square of the chess board, two grains on the second, four grains on the third and so on, so that each square contained twice that one the one before. There are 64 squares on a chess board. Create a program that calculates (recursively) the total amount of grains on the 64^th square. Remember to add Pre and Post conditions to your program.

10.     The enrollment at the local university is currently 5678. From now on, the university will graduate 24% of its students and add 1250 new ones. What will the enrollment be during the sixth year? What will the enrollment be in the long run? Create a program that would help you solve this problem recursively.