# 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 | + | {** |

+ | 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 | ||

− | // | + | // optimization: then part gets executed most of the time |

if n > 1 then | if n > 1 then | ||

− | + | begin | |

− | + | fibonacci := fibonacci(n - 2) + fibonacci(n - 1); | |

− | + | end | |

− | |||

else | else | ||

− | result := | + | 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 | + | This one is preferable for its run-time behavior. |

− | + | <syntaxhighlight lang="pascal"> | |

− | <syntaxhighlight> | + | {** |

− | function | + | 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 | ||

− | + | /// temporary iterator variable | |

+ | i: longword; | ||

+ | /// holds preceding fibonacci values | ||

+ | f: array[relativePosition] of qword; | ||

begin | 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; | end; | ||

</syntaxhighlight> | </syntaxhighlight> | ||

− | == | + | == 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;
```