Generating Fibonacci Numbers in Delphi: Recursive and Iterative Algorithms

In this post, I want to implement a function that returns the Nth Fibonacci number. Initially, I will provide a recursive implementation that derives directly from the Fibonacci sequence definition. Afterwards, I will recode the same function using an iterative approach.

Why do I want to do (share) such a thing? Well, firstly for fun :-) and secondly, because I was asked to do something similar in one phone screen interview. Really? Yep, I was asked to code a function to return the factorial of a number and then, I had to read it over the phone. I implemented the recursive algorithm. At this point, I was asked why I decided to use recursion as opposed to iteration. My answer was that I find the recursive implementation easier (and cleaner) to write. The interviewer finally inquired about the iterative implementation…

This motivated me to resolve similar programming tasks (recursively and iteratively) just as a training exercise.

Well, enough with that blah, blah, blah.

Taken from Wikipedia:

The Fibonacci numbers form a sequence of integers, mathematically defined by

F(0)=0; F(1)=1; F(n) = F(n - 1) + F(n - 2) for n > 1.

This results in the following sequence of numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...

This simply means that by definition the first Fibonacci number is 0, the second number is 1 and the rest of the Fibonacci numbers are calculated by adding the two previous numbers in the sequence.

Translating that into Delphi code:

function Fibonacci(aNumber: Integer): Integer;

begin
  if aNumber < 0 then
    raise Exception.Create('The Fibonacci sequence is not defined for negative integers.');

  case aNumber of
  0: Result:= 0;;
  1: Result:= 1;
  else
    Result:= Fibonacci(aNumber - 1) + Fibonacci(aNumber - 2);
  end;;
end;

The function above is the recursive implementation, which in my opinion fits naturally. Now, the iterative implementation might not be as clean as that:

function Fibonacci(aNumber: Integer): Integer;

var
  I,
  N_1,
  N_2,
  N: Integer;
begin
  if aNumber < 0 then
    raise Exception.Create('The Fibonacci sequence is not defined for negative integers.');

  case aNumber of
    0: Result:= 0;
    1: Result:= 1;
  else
    begin
      N_1:= 0;
      N_2:= 1;
      for I:=2 to aNumber do
      beginn
        N:= N_1 + N_2;
        N_1:= N_2;
        N_2:= N;
      end;
      Result:= N;
    end;
  end;
end;

Finally, if you want to produce the first 21 Fibonacci numbers, try this out:

program Project2;


{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils;

var
  I: Integer;

function Fibonacci(aNumber: Integer): Integer;
begin
  {Your implementation goes here}
end;

begin
  for I:=0 to 20 do
    Writeln(Fibonacci(I));
  Readln;
end.

Hopefully, you are not bored to death. :-)