Handouts Addendum Fundamentals of Algorithms CS502 Lecture: 16 Page No: 74 Topic: Fibonacci Sequence Fk-1 Error: Correction: A single recursive call to fib(n) results in one recursive call to fib(n two recursive − 1), calls to fib(n three recursive calls to fib(n five recursive calls to fib(n and, − 2), − 3), − 4) in general, recursive calls to fib(n For each call, we’re recomputing the same Fk+1 − k) fibonacci number from scratch.
Handouts Addendum Fundamentals of Algorithms CS502 Lecture: 16 Page No: 74 Topic: Fibonacci Sequence Error: Fk-1 Correction: A single recursive call to fib(n) results in one recursive call to fib(n − 1), two recursive calls to fib(n − 2), three recursive calls to fib(n − 3), five recursive calls to fib(n − 4) and, in general, Fk+1 recursive calls to fib(n − k) For each call, we’re recomputing the same fibonacci number from scratch.