Computing Fibonacci NumbersNow we only compute each Fibonacci number once. Our evatuation tree looks something like this, where we've cut out all of the duplicate nodes. Each number starting from requires doing one addition (and two lookups, but lookups are fast), so we can compute using additions.
Now we only compute each Fibonacci number once. Our evatuation tree looks something like this, where we've cut out all of the duplicate nodes. Each number starting from requires doing one addition (and two lookups, but lookups are fast), so we can compute using additions.