CSC148H5 Lecture Notes - Lecture 11: Stack Overflow, Memoization
Document Summary
Fibonacci sequence / number a sequence of numbers where every number after the first two is the sum of the two preceding ones. The 0th and 1st numbers are 0 and 1 (base cases). The n-th number in the fibonacci sequence is called the n-th fibonacci number. e. g. , fib(n) We want to write a program to, given n, compute fib(n) Memoization a general technique to avoid redoing the same work over and over again. Store the results of recursive calls (e. g. , in a dictionary) as are being computed. When making a function call, first look up the result in the dictionary rather than setting off a chain of recursive calls again. Right now, the runtime for fib we have is o(n) There is a way to do it in o(log n) time. It will require some 2nd-year csc and mat courses to fully understand (involving optimized matrix chain multiplication)
