(a) Write a function that computes the following recursive function (written here in traditional mathematical notation):
f(0) = 1 f(-1) = 0 f(-2) = 0 f(-3) = 0 f(m) = f(m-1) + f(m-2) + f(m-3) - f(m-4) for m >= 1
What are the values of f(28), f(29), and f(30)? How long does it take to compute each of these values? Use the Scheme function time to measure how long an evaluation takes. (Example: (time (f 0)))
(b) In a functional language without side-effects or assignments, the value of a function always depends solely on its arguments. This allows us to use an optimization known as memoizing. You can pass a list of previous answers (a "memo") as a parameter that the function can use to speed its work. Write an Scheme function called fastF that is a solution to part (a) using memoizing. How long does it take now to compute your answer?
You must use recursion, and not iteration. You may not use side-effects (e.g. set!).
Submit your code in a file called memoization.scm.