Difference between revisions of "Fibonacci number"

From Free Pascal wiki
(review)
Line 1: Line 1:
{{Fibonacci_number}}
+
{{Fibonacci number}}
 
 
= Fibonacci number =
 
  
 
The Fibonacci Sequence is the series of numbers:
 
The Fibonacci Sequence is the series of numbers:
  
  0, 1, 1, 2, 3, 5, 8, 13, 21, ...
+
  0, 1, 1, 2, 3, 5, 8, 13, 21,
  
The idea is to add the two last numbers, and thus get the next value.
+
The idea is to add the two last numbers in order to produce the next value.
 
 
== Recursive way ==
 
  
 +
== recursive implementation ==
 
<syntaxhighlight>
 
<syntaxhighlight>
 
+
function FibonacciNumber(const n: integer): integer;
function FibonacciNumber( n : integer ): integer;
 
 
begin
 
begin
  if n > 1 then result := ( FibonacciNumber( n - 1 ) + FibonacciNumber( n - 2 ) )
+
// recursive case
    else
+
if n > 1 then
      if n = 0 then result := 0
+
result := (FibonacciNumber(n-1) + FibonacciNumber(n-2))
        else result := 1;
+
// base case
end;  
+
else if n = 0 then
 
+
result := 0
 +
else
 +
result := 1;
 +
end;
 
</syntaxhighlight>
 
</syntaxhighlight>
  
== Iterative way ==
+
== iterative implementation ==
This one is preferable.
+
This one is preferable for its run-time behaviour.
  
 
<syntaxhighlight>
 
<syntaxhighlight>
 
 
function Fibonacci(n: Integer): Integer;
 
function Fibonacci(n: Integer): Integer;
 
var
 
var
Line 34: Line 32:
 
   if n <= 0 then
 
   if n <= 0 then
 
     exit(0);
 
     exit(0);
   if n = 1 then  
+
   if n = 1 then
    exit(1);
+
    exit(1);
 
   u := 0;
 
   u := 0;
 
   v := 1;
 
   v := 1;
   for i := 2 to n do  
+
   for i := 2 to n do
 
   begin
 
   begin
 
     w := u + v;
 
     w := u + v;
Line 45: Line 43:
 
   end;
 
   end;
 
   Result := v;
 
   Result := v;
End;  
+
end;
 
 
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 
== See also ==
 
== See also ==
+
* [https://oeis.org/A000045 Fibonacci numbers in the on-line encyclopedia of integer sequences]
* [http://www.freepascal.org/docs-html/prog/progsu151.html   Some assembly routine which uses the C calling convention that calculates the nth Fibonacci number]  
+
* [https://freepascal.org/docs-html/current/prog/progsu150.html Some assembly routine which uses the C calling convention that calculates the nth Fibonacci number]
* [[Solution_3| Tao Yue Solution to Fibonacci Sequence Problem]]  
+
* [[Solution 3|Tao Yue Solution to Fibonacci Sequence Problem]]
  
 
[[Category:Mathematics]]
 
[[Category:Mathematics]]

Revision as of 18:42, 27 January 2018

Deutsch (de) English (en) suomi (fi) français (fr) русский (ru)

The Fibonacci Sequence is the series of numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, …

The idea is to add the two last numbers in order to produce the next value.

recursive implementation

function FibonacciNumber(const n: integer): integer;
begin
	// recursive case
	if n > 1 then
		result := (FibonacciNumber(n-1) + FibonacciNumber(n-2))
	// base case
	else if n = 0 then
		result := 0
	else
		result := 1;
end;

iterative implementation

This one is preferable for its run-time behaviour.

function Fibonacci(n: Integer): Integer;
var
  i,u,v,w: Integer;
begin
  if n <= 0 then
    exit(0);
  if n = 1 then
    exit(1);
  u := 0;
  v := 1;
  for i := 2 to n do
  begin
    w := u + v;
    u := v;
    v := w;
  end;
  Result := v;
end;

See also