Fibonacci number

From Free Pascal wiki
Revision as of 17:42, 27 January 2018 by Kai Burghardt (talk | contribs) (review)
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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