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:
- Briefly discuss why the recursive Fibonacci solution from #6 isn't terribly
efficient.
- 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?
- Memoization is almost like the old stand-by of removing recursion
by using a stack ADT with a loop. How are they different?
- Another technique to make recursion more efficient is called
tail
recursion.
Explain this technique and use it to fix the Fibonacci problem
from #6.
- 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.