2. Fibonacci Sequence

l  Problem

Fibonacci sequence is the series of numbers: 1, 1, 2, 3, 5, 8, 13, 21 …

From the third number, each number is found by adding up the two numbers before it.

Please output the first N terms of this sequence by using three algorithms, namely, iteration, recursion, and esProc sequence along with insert function.

 

l  Tip

General steps: Define a sequence and assign 1 to the first two terms; then loop through it for N times, respectively obtaining the last term and the last but one term and add their sum to the sequence. By doing so, a Fibonacci sequence will be generated.

1.  Define the number of members in a Fibonacci sequence.

2.  Use the iterative algorithm to declare an integer sequence that has only two members whose values are both 1. Loop through it for N-2 times, and, in the loop body, add the sum of the last term and the last but one term to the end of the sequence.

3.  Use the recursion algorithm to declare two parameters a and b, assign 0 and 1 to them respectively. Loop them for N times to recursively compute a and b. New b is obtained by adding up Old a and Old b, and New a is found by assigning Old b to it and returned as a member of the resulting sequence.

4.  Use the esProc subroutine, in which the parameter is N. When the number of the members in the sequence is less than or equal to 2, return [1,1] to end the computation. When the number is greater than 2, recursively invoke the subroutine and append the sum of the last two terms to the end of the sequence. Continue the recursion until the number of members in the sequence is 2.

 

l  Code

 

A

B

C

 

1

30

 

 

Declare the quantity of Fibonacci Series

2

/Iterative algorithm

 

 

3

=[1,1]

 

Define the sequence.

4

for A1-2

=A3.m(-1)+A3.m(-2)

>A3=A3|B4

Loop it for A1-2 times, add the last term and the last but one term in A3, and add the sum to A3.

5

/Recursion algorithm

 

 

 

6

>a=0,b=1

 

 

Declare two parameters, and assign 0 and 1 to them respectively.

7

=A1.((b=a+b,a=b-a))

 

 

Loop it for A1 times, recursively compute a and b, and compute New b = Old a + Old b, and assign the Old b to the New a, return the New a as the member of the result sequence.

8

/esProc function, the parameter is the quantity of the series.

 

 

 

9

=func(A10,A1)

 

 

Invoke A10 subroutine, and the parameter is A1.

10

func

if A10<=2

return A10*[1]

Loop the parameter values and return sequence [1, 1] when the parameter values are smaller than 2.

11

=func(A10,A10-1)

return B11 | (B11.m(-1) + B11.m(-2))

 

Recursively invoke A10 subroutine and overlap the sum of the last two terms to 

B11 until A10 is 2.

 

l  Result