Computing Fibonacci NumbersWe can see how evaluating a single Fibonacci number fans out into evaluating more and more numbers below it. This is enormously wasteful: we evaluate three times, for example. At most, to evaluate , we should need to evaluate every Fibonacci number below it. We're doing worse than that!
We can see how evaluating a single Fibonacci number fans out into evaluating more and more numbers below it. This is enormously wasteful: we evaluate three times, for example. At most, to evaluate , we should need to evaluate every Fibonacci number below it. We're doing worse than that!