Itanium® Architecture for Programmers: Understanding 64-Bit Processors and EPIC Principles

11.7. Recursion for Fibonacci Numbers Revisited

We presented recursive and nonrecursive functions for computing numbers in the Fibonacci sequence in Chapter 10, representing two extreme computational models. Now we revisit the Fibonacci sequence with another algorithm adapted from a Pascal illustration by Rohl that avoids the unfortunate computational time for the branching form of recursion, while still being recursive in nature.

For convenience in setting up this algorithm, the correspondence between the index position n and each Fibonacci number F_n in the sequence will begin with a zeroth member, as follows:

					n        0        1        2        3        4        5        6        7        8       
 9        ...
Fn 0 ...