Fibonacci Numbers : An Introduction

 

Fibonacci Numbers

Fibonacci numbers denote a sequence of numbers that go under the name of Italian mathematician Leonardo Fibonacci.1 More precisely, these numbers are known as Fibonacci sequence, and the numbers that belong to this are called Fibonacci numbers. The sequence actually has quite a simple definition, namely:

F(1) = 1,

F(2) = 1,

F(n) = F(n − 1) + F(n − 2) (for n > 2).

In concrete terms, the sequence can be enumerated as 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . .. The Fibonacci sequence F(n) is known to attract widespread interest for frequently appearing as a numerical model when we try to build models representing natural phenomena, such as the arrangement of seeds in sunflowers, the number of rabbit siblings, and others. Let us deepen our understanding of recursive calls using this sequence. At the same time, let us discover the limitations of recursive calls and introduce further refinements.

2.2.1 Computing Fibonacci Numbers F(n) Arising from

Recursive Calls

There is one particular aspect that must be considered carefully when working with recursive calls.We have seen that, in recursive calls, the algorithm capable of solving its own partial problem is reused. It is worth noting to what extent this “partial problem” is necessary. In the Tower of Hanoi problem, we reused the algorithm for solving the partial problem of size n − 1 to solve a problem of size n. Considering the definition of Fibonacci numbers F(n), the values of both F(n − 1) and F(n − 2) are required. From this fact, we learn that it does not suffice to show a clear solution for the small partial problem in n = 1, but the solutions for n = 1 and n = 2 are 1  also needed. If we construct the algorithm according to its definition while paying attention to this point, we obtain the algorithm below. Using this algorithm, the n-th Fibonacci number F(n) can be obtained by calling Fibr(n), which produces the returned value as its output.

Algorithm 13: recursive algorithm Fibr(n) to compute the n-th Fibonacci number

F(n)

Input : n

Output: the n-th Fibonacci number F(n)

1 if n = 1 then return 1;

2 if n = 2 then return 1;

3 return Fibr(n − 1) + Fibr(n − 2);

Exercise 20 Implement and execute the algorithm above. How will the

program behave when n is made slightly larger (by a few tens)?

2.2.2 Execution Time of Fibr Based on Recursive Calls

When we implement and execute Fibr(n), execution clearly slows down for values around n = 40 and above. Why does this occur? Let us consider an execution time tF (n). When considering execution times, examining the recursive equation is inevitable. In concrete terms, we have:

• For n = 1: a constant time tF (1) = c1

• For n = 2: a constant time tF (2) = c2

• For n > 2: for a given constant c3, tF (n) = tF (n − 1) + tF (n − 2) + c3

Here, the value of the constant itself has no meaning, and therefore, we can simply

denote them as c. By adding c to both sides of the equation, for n > 2 we can write:

tF (n) + c = (tF (n − 1) + c) + (tF (n − 2) + c)

which is exactly equivalent to the definition of Fibonacci numbers. In other words,

the execution time tF (n) of Fibr(n) can be considered proportional to the value of

Fibonacci numbers.  it is known that Fibonacci numbers F(n) will be F(n) ∼ _(1.618n). In other words, Fibonacci numbers constitute an exponential function. Therefore, if we compute Fibonacci numbers according to their definition, the computation time tends to increase exponentially, that is, if n becomes larger, the computation time of a naïve implementation is excessively large.

2.2.3 Fast Method for Computing Fibonacci Numbers

We learnt that, according to the definition, the time required to compute Fibonacci numbers increases exponentially. However, some readers may feel intrigued by that. For instance, to compute F(9), only F(8) to F(1) suffice. First, let us solve the question why  the time required for computing Fibonacci numbers increases exponentially. For example, F(9) can be computed if F(8) and F(7) are available. Computing F(8) only requires knowing F(7) and F(6), and computing F(7) only requires F(6) and F(5), and so forth. This calling mechanism is illustrated in image

 

What we need to note here is “who is callingwho.” For instance, if we pay attention to F(7), this value is called twice, that is, upon the computation of both F(9) and F(8). That is, F(7) is nested twice to compute F(9). Likewise, F(6) is called from F(8) and F(7), and F(7) is called twice. This structure becomes more evident as we approach the leaves of the tree structure. F(2) and F(3) appear in Figure remarkably often. Thus, the Fibr(n) algorithm based on recursive calls computes the same value over and over again in a wasteful fashion.

Algorithm 14: Algorithm Fiba(n) to compute the n-th Fibonacci number F(n)

using array Fa[]

Input : n

Output: n-th Fibonacci number F(n)

1 Fa[1] ←1;

2 Fa[2] ←1;

3 for i ← 3, 4, . . . , n do

4 Fa[i] ← Fa[i − 1] + Fa[i − 2];

5 end

6 output Fa[n];

 

First, F(1) and F(2) are directly computed when i = 1, 2. Then, for i > 2 it is quite clear that for computing Fa[i ] we already have the correct values of Fa[i − 1] and Fa[i − 2]. These two observations indicate to us that Fibonacci numbers can be correctly computed by this algorithm. Therefore, the computation time of the Fiba(n) algorithm is linear, that is, proportional to n, which means it is extremely fast. Let us stop for a while to think ahead. For i > 2, what is necessary for computing F(i ) is F(i − 1) and F(i − 2), and elements further behind are not needed. In other words, provided that we keep in mind the last two elements, the array itself is unnecessary. With that perception in mind, we can write an even more efficient algorithm (from the viewpoint of memory space).

Algorithm 15: Algorithm Fib2(n) to compute the n-th Fibonacci number F(n)

without using arrays

Input : n

Output: n-th Fibonacci number F(n)

1 if n < 3 then

2 output “1”;

3 else

4 Fa1 ← 1 ; /* Memorize F(1) */

5 Fa2 ← 1 ; /* Memorize F(2) */

6 for i ← 3, 4, . . . , n do

7 Fa ← Fa2 + Fa1 ; /* Compute/memorize F(i ) = F(i − 1) + F(i − 2) */

8 Fa1 ← Fa2 ; /* Update F(i − 2) with F(i − 1) */

9 Fa2 ← Fa ; /* Update F(i − 1) with F(i ) */

10 end

11 output Fa;

12 end