12,827,730 members (48,729 online)
Technical Blog
alternative version

#### Stats

6.6K views
1 bookmarked
Posted 17 Dec 2012

# Generating Fibonacci Numbers in Delphi: Recursive and Iterative Algorithms

, 17 Dec 2012 CPOL
 Rate this:
A function that returns the Nth Fibonacci number

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));
end.```

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

## About the Author

 Software Developer Digital Rapids Canada
My name is Yanniel Alvarez Alfonso. I was born in San Antonio de los Baños, Havana Province, Cuba on October 24th, 1982.

I majored in Information Technology Engineering at José Antonio Echeverría Polytechnic Institute (CUJAE) in Havana City, Cuba (July 2006). After that, I got a Masters Degree in Applied Computer Science at the same University (May 2009).

I used to work as a professor of Information Technology at CUJAE. Right now, I work as a Software Developer in Toronto, Canada. I moved to Canada under the Skilled Worker Program on February 26th, 2010.

This is my personal blog: Yanniel's notes; in which I write about miscellaneous topics.

The link at the end of this sentence compiles an index of all the articles I have written so far about Delphi Programming.

 Pro

## Comments and Discussions

 -- There are no messages in this forum --