Write a recursive method factorial that takes an
int argument n and returns n! as
a long. Recall that 0! = 1 and
n! = n * (n - 1)!. No loops.
Write the obvious recursive method fibonacci that takes an
int argument n and returns the
nth Fibonacci number as a long. The sequence is
0, 1, 1, 2, 3, 5, 8, 13, …: after 0 and
1, each number is the sum of the previous two, so
fibonacci(0) = 0, fibonacci(1) = 1, and
otherwise fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2).
No loops. This one is only tested on small n.
Write a non-recursive method iterativeFibonacci that takes
an int n and returns as a long,
computing the same answer as fibonacci but using a loop
instead of recursion. Keep track of the last two numbers as you go. This
one is tested up to n = 90.
Write a recursive method fastFibonacci that takes an
int n and returns the nth Fibonacci
number as a long, following basically the same sequence of
computations as your loop—but using recursion instead of a loop. You will
probably want to write a helper method that actually does the recursion.
But no loops are allowed anywhere, including in the helper.
Write a recursive method change that takes an
int amount of money and a List<Integer>
of coin denominations (e.g. 1, 5, 10, 25, 50) and returns,
as a long, the number of ways to make that amount with some
combination of those kinds of coins. The signature is:
public long change(int amount, List<Integer> coins)Don’t worry about combinatorial explosion yet; just get the recursion working.
Write a method iterativeChange with the arguments and return
type as change that computes the same answer using a loop.
The trick is to use the same idea as iterativeFibonacci:
build the answer up from the small cases instead of breaking the big case
down. Just like the iterative Fibonacci needed to use some variables to
keep track of where it was, you’ll need to do the same thing here though
perhaps in a slightly more complex way.
These are more advanced recursion problems than the recursive methods set. The first couple are are ordinary recursion. But the rest require some cleverness to avoid combinatorial explosion which the tests will test for.
The methods in this set take int arguments but
return long because the values they compute get big fast.