Difference between revisions of "Fibonacci number"

From Free Pascal wiki
(review)
(blow up)
Line 2: Line 2:
  
 
The Fibonacci Sequence is the series of numbers:
 
The Fibonacci Sequence is the series of numbers:
 
+
<syntaxhighlight lang="pascal">
 
  0, 1, 1, 2, 3, 5, 8, 13, 21, …
 
  0, 1, 1, 2, 3, 5, 8, 13, 21, …
 
+
</syntaxhighlight>
 
The idea is to add the two last numbers in order to produce the next value.
 
The idea is to add the two last numbers in order to produce the next value.
  
 
== recursive implementation ==
 
== recursive implementation ==
<syntaxhighlight>
+
<syntaxhighlight lang="pascal">
function FibonacciNumber(const n: integer): integer;
+
{**
 +
implements Fibonacci sequence recursively
 +
 +
\param n the index of the Fibonacci number to retrieve
 +
\returns the Fibonacci value at n
 +
}
 +
function fibonacci(const n: byte): qword;
 
begin
 
begin
// recursive case
+
// optimization: then part gets executed most of the time
 
if n > 1 then
 
if n > 1 then
result := (FibonacciNumber(n-1) + FibonacciNumber(n-2))
+
begin
// base case
+
fibonacci := fibonacci(n - 2) + fibonacci(n - 1);
else if n = 0 then
+
end
result := 0
 
 
else
 
else
result := 1;
+
begin
 +
// since the domain is restricted to non-negative integers
 +
// we can bluntly assign the result to n
 +
fibonacci := n;
 +
end;
 
end;
 
end;
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 
== iterative implementation ==
 
== iterative implementation ==
This one is preferable for its run-time behaviour.
+
This one is preferable for its run-time behavior.
 
+
<syntaxhighlight lang="pascal">
<syntaxhighlight>
+
{**
function Fibonacci(n: Integer): Integer;
+
implements Fibonacci sequence iteratively
 +
 +
\param n the index of the Fibonacci number to calculate
 +
\returns the Fibonacci value at n
 +
}
 +
function fibonacci(const n: longword): qword;
 +
type
 +
/// more meaningful identifiers than simple integers
 +
relativePosition = (previous, current, next);
 
var
 
var
  i,u,v,w: Integer;
+
/// temporary iterator variable
 +
i: longword;
 +
/// holds preceding fibonacci values
 +
f: array[relativePosition] of qword;
 
begin
 
begin
  if n <= 0 then
+
f[previous] := 0;
    exit(0);
+
f[current] := 1;
  if n = 1 then
+
    exit(1);
+
// note, in Pascal for-loop-limits are inclusive
  u := 0;
+
for i := 1 to n do
  v := 1;
+
begin
  for i := 2 to n do
+
f[next] := f[previous] + f[current];
  begin
+
f[previous] := f[current];
    w := u + v;
+
f[current] := f[next];
    u := v;
+
end;
    v := w;
+
  end;
+
// assign to previous, bc f[current] = f[next] for next iteration
  Result := v;
+
fibonacci := f[previous];
 
end;
 
end;
 
</syntaxhighlight>
 
</syntaxhighlight>
  
== See also ==
+
== see also ==
 
* [https://oeis.org/A000045 Fibonacci numbers in the on-line encyclopedia of integer sequences]
 
* [https://oeis.org/A000045 Fibonacci numbers in the on-line encyclopedia of integer sequences]
 
* [https://freepascal.org/docs-html/current/prog/progsu150.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]
 +
* [https://rosettacode.org/wiki/Fibonacci_sequence#Pascal Fibonacci sequence § “Pascal” on RosettaCode.org]
 
* [[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 01:27, 7 November 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

{**
	implements Fibonacci sequence recursively
	
	\param n the index of the Fibonacci number to retrieve
	\returns the Fibonacci value at n
}
function fibonacci(const n: byte): qword;
begin
	// optimization: then part gets executed most of the time
	if n > 1 then
	begin
		fibonacci := fibonacci(n - 2) + fibonacci(n - 1);
	end
	else
	begin
		// since the domain is restricted to non-negative integers
		// we can bluntly assign the result to n
		fibonacci := n;
	end;
end;

iterative implementation

This one is preferable for its run-time behavior.

{**
	implements Fibonacci sequence iteratively
	
	\param n the index of the Fibonacci number to calculate
	\returns the Fibonacci value at n
}
function fibonacci(const n: longword): qword;
type
	/// more meaningful identifiers than simple integers
	relativePosition = (previous, current, next);
var
	/// temporary iterator variable
	i: longword;
	/// holds preceding fibonacci values
	f: array[relativePosition] of qword;
begin
	f[previous] := 0;
	f[current] := 1;
	
	// note, in Pascal for-loop-limits are inclusive
	for i := 1 to n do
	begin
		f[next] := f[previous] + f[current];
		f[previous] := f[current];
		f[current] := f[next];
	end;
	
	// assign to previous, bc f[current] = f[next] for next iteration
	fibonacci := f[previous];
end;

see also