go to previous page   go to home page   go to next page

Answer:

Of course.


Dynamic Thinking

Fibonacci Calling Sequence

Say that main() has called fib(5). The diagram shows the activations, their parameters (in blue), and their return values (in red). Pick an activation and study how the activations below it correspond to the code.

To see the dynamic sequence of activations, repeatedly click on the diagram. A solid circle represents an activation that is currently computing or waiting for a result to be returned.

A dotted circle represents an activation that has finished its computation and is no longer on the activation chain.

The diagram labeled All Activations shows how each activation (except for the base cases) is supported by two other activations.

At any time in the execution of fib(5) the activations that have not yet finished their computation (because they are waiting for a value) form a single chain. There is never more than one activation chain. The activation chain bends left and right, but there is always a single successor and a single predecessor for each link (except for the first activation which has not predecessor and for the base cases which have no successors.)


QUESTION 20:

For fib(5), 9 activations occur. Examine the diagram. Do you imagine that for fib(n) that there are many more than n activations.


go to previous page   go to home page   go to next page