Data Structures and Algorithms with Object-Oriented Design Patterns in C++

## Example-Generalized Fibonacci Numbers

Consider the problem of computing the generalized Fibonacci numbers  . The generalized Fibonacci numbers of order are given by

Notice that the ``normal'' Fibonacci numbers considered in Section  are the same as the generalized Fibonacci numbers of order 2.

If we write a recursive function that implements directly Equation , we get an algorithm with exponential running time. For example, in Section  it is shown that the time to compute the second-order Fibonacci numbers is .

The problem with the direct recursive implementation is that it does far more work than is needed because it solves the same subproblem many times. For example, to compute it is necessary to compute both and . However, in computing it is also necessary to compute , and so on.

An alternative to the top-down recursive implementation is to do the calculation from the bottom up. In order to do this we compute the series of sequences

Notice that we can compute from the information contained in simply by using Equation .

Program  defines the function Fibonacci which takes two integer arguments n and k and computes the Fibonacci number of order k using the approach described above. This algorithm uses an array to represent the series of sequences . As each subsequent Fibonacci number is computed it is added to the end of the array.

Program: Dynamic Programming Example--Computing Generalized Fibonacci Numbers

The worst-case running time of the Fibonacci routine given in Program  is a function of both n and k: