# 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

The following implementations show the principle of how to calculate Fibonacci numbers. They lack of input checks. Depending on your preferences you might either want to generate a run-time error (e.g. by `{\$rangeChecks on}` or utilizing `system.runError`), raise an exception, or simply return a bogus value indicating something went wrong.

### recursive implementation

``` 3 type
4 	/// domain for Fibonacci function
5 	/// where result is within nativeUInt
6 	// You can not name it fibonacciDomain,
7 	// since the Fibonacci function itself
8 	// is defined for all whole numbers
9 	// but the result beyond F(n) exceeds high(nativeUInt).
10 	fibonacciLeftInverseRange =
11 		{\$ifdef CPU64} 0..93 {\$else} 0..47 {\$endif};
12
13 {**
14 	implements Fibonacci sequence recursively
15
16 	\param n the index of the Fibonacci number to retrieve
17 	\returns the Fibonacci value at n
18 }
19 function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
20 begin
21 	// optimization: then part gets executed most of the time
22 	if n > 1 then
23 	begin
24 		fibonacci := fibonacci(n - 2) + fibonacci(n - 1);
25 	end
26 	else
27 	begin
28 		// since the domain is restricted to non-negative integers
29 		// we can bluntly assign the result to n
30 		fibonacci := n;
31 	end;
32 end;
```

### iterative implementation

This one is preferable for its run-time behavior.

```12 {**
13 	implements Fibonacci sequence iteratively
14
15 	\param n the index of the Fibonacci number to calculate
16 	\returns the Fibonacci value at n
17 }
18 function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
19 type
20 	/// more meaningful identifiers than simple integers
21 	relativePosition = (previous, current, next);
22 var
23 	/// temporary iterator variable
24 	i: longword;
25 	/// holds preceding fibonacci values
26 	f: array[relativePosition] of nativeUInt;
27 begin
28 	f[previous] := 0;
29 	f[current] := 1;
30
31 	// note, in Pascal for-loop-limits are inclusive
32 	for i := 1 to n do
33 	begin
34 		f[next] := f[previous] + f[current];
35 		f[previous] := f[current];
36 		f[current] := f[next];
37 	end;
38
39 	// assign to previous, bc f[current] = f[next] for next iteration
40 	fibonacci := f[previous];
41 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.