Fibonacci number

│ 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.

generation

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;

lookup

While calculating the Fibonacci number every time it is needed requires almost no space, it takes a split second of time. Applications heavily relying on Fibonacci numbers definitely want to use a lookup table instead. And yet in general, do not calculate what is already a known fact. Since the Fibonacci sequence doesn't change, actually calculating it is a textbook demonstration but not intended for production use.

Nevertheless an actual implementation is omitted here, since everyone wants to have it differently, a different flavor.

see also

• Fibonacci numbers in the on-line encyclopedia of integer sequences
• Some assembly routine which uses the C calling convention that calculates the nth Fibonacci number
• Fibonacci sequence § “Pascal” on RosettaCode.org
• Tao Yue Solution to Fibonacci Sequence Problem