Biology Reference
In-Depth Information
Fig. 2 (a) Top-down and (b) bottom-up recursive computations of Fibonacci
numbers
and
F
(3) are called recursively. Each function is called recursively
until they meet
F
(0) and
F
(1) as shown in the graphical representa-
tion. Adding up these functions and traversing back to the top node
F
(5) will return the fifth Fibonacci number. From this tree
structured graph, it can be seen that
F
(2) and
F
(3) are computed
three times and two times, respectively, by different function call-
ings. A total of seven summation operations are performed. How-
ever, if we operated considering a space-time trade-off by saving
F
(2) and
F
(3) as they were evaluated, less number of evaluations
would be required. This can be achieved by following a bottom-up
recursive approach. According to the bottom-up scheme, the
computation starts
from the known function values
and
F
is evaluated and saved. Calling previously
memorized function values as they are required in the recursive
function, the next Fibonacci number is evaluated iteratively until
the desired number is met. We can see the bottom-up recursion in
Fig.
2b
. Here, the graph structure forms a trellis instead of a tree
structure as in the top-down approach.
F
(2) is evaluated once and
called from the memory for the computation of
F
(3) and
F
(4).
Same is true for
F
(3) which is used in the computation of
F
(4) and
F
(5). A total of four summation are performed. When this scheme is
generalized, the top-down approach will require
F
ð
2
Þ¼
F
ð
1
Þþ
F
ð
0
Þ
1
summations for the computation of
F
(
n
), where the bottom-up
approach requires
n
ð
n
þ
1
Þ
1 summations for the same computation.
The introduction of memory and single computation of duplicated
function instances by bottom-up recursion is the fundamental
methodology of dynamic programming. Similar to the Fibonacci
number computation, dynamic programming can provide signifi-
cant reduction in computational complexity for similar recursive
problems where overlapping subproblems are observed.
