Do the Even questions from section 8.3.3. #6 means the 'PROC' should result in the Nth Fibonacci number where N is the input parameter. Hint on #4: check out this related lab.

(It wouldn't hurt if you studied the answers to the odd questions as well.)

In addition, do these problems:

  1. Briefly discuss why the recursive Fibonacci solution from #6 isn't terribly efficient.
  2. Briefly read a few articles describing memoization (no, that's not a mis-spelling!). Discuss how this works to make recursion more efficient. What limitations does memoization itself face? How could it help with the Fibonacci problem from #6?
  3. Memoization is almost like the old stand-by of removing recursion by using a stack ADT with a loop. How are they different?
  4. Another technique to make recursion more efficient is called tail recursion. Explain this technique and use it to fix the Fibonacci problem from #6.
  5. In lecture we discussed how to discover the point at which a recursion might crash. What (two) values do you need to calculate this? What calculation do you do with them?

This assignment is Level 4.