Fibonacci number

From Free Pascal wiki
Revision as of 17:42, 27 January 2018 by Kai Burghardt (talk | contribs) (review)

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