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 me 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 cleaner 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
      begin
        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 :-)

CodeProject

Internationalizing your Delphi application: An ABC example

If you want to make your Delphi application general enough to address multiple locales, then you need to internationalize it. There are three common aspects that I want to emphasize (no necessarily in that order):

• Resourcing
• Unit conversions
• Dynamic messages

We’ll cover the three of them with a very simple example. Consider the following code snipped intended for the en-US locale (English-United States of America):

procedure TForm1.DefineFever;
begin
  ShowMessage('If the body temperature rises above 99°F the person is considered to have a fever.');
end;

Resourcing is the process of removing hard-coded strings from the code by making them resourcestrings instead.

The code above is not localizable because the ShowMessage procedure is taking a hard-coded string. What do you do? Take a look:

procedure TForm1.DefineFever;
resourcestring
  strFeverDefinition = 'If the body temperature rises above 99°F the person is considered to have a fever.';
begin
  ShowMessage(strFeverDefinition);
end;

We defined strFeverDefinition as a resourcestring and used it as a parameter for the ShowMessage procedure. The functionality remains the same, but the function is now localizable.

Unit conversions: In some countries (like the United States and Belize) the temperature is given in the Fahrenheit scale, but in the rest is given in the Celsius scale. In order to internationalize this we can do the following:

function GetFeverTemperature: string;
var
  LangID: LangID;
begin
  //By default
  Result:= '37.2°C';

  {read current system locale}
  LangID := GetSystemDefaultLangID;

  //Assuming that only the United States and Belize use the Fahrenheit scale
  if (LangID = {English - United States} 1033) or        
     (LangID = {English - Belize} 10249) then
  Result:= '99°F';
end;

procedure TForm1.DefineFever;
begin
  ShowMessage('If the body temperature rises above ' + GetFeverTemperature + ' the person is considered to have a fever');
end;

Wait a minute, we managed the unit conversion by introducing a dynamic message, but we reintroduced the hard-coded strings. That’s not good!

Dynamic messages: We consider the ShowMessage above to be a dynamic message, because the parameter depends on the GetFeverTemperature function, which of course can vary. 

To solve the pitfall above we can refactor the DefineFever function as follows:  

procedure TForm1.DefineFever;
resourcestring
  strFeverDefinition = 'If the body temperature rises above %0:s the person is considered to have a fever.';
begin
  ShowMessage(Format(strFeverDefinition, [GetFeverTemperature]));
end;

We are just using a format string (resourcestring) that we can format by using the Format routine. This allows resourcing and handling the dynamic message all at once.

The thing about dynamic messages goes beyond. In Spanish, for instance, the dynamic message would have been coded as follows:

ShowMessage('Se considera que la persona tiene fiebre si la temperatura corporal es superior a ' + GetFeverTemperature);

Note that the GetFeverTemperature is at the end of the ShowMesssage parameter, as opposed to the English implementation that has it in the middle. There’s no way you can localize something like this if you don’t internationalize it first.

So the ABC for Delphi localization is Resourcing, Unit Conversions and Dynamic Messages. 

CodeProject

Multiton Design Pattern in Delphi

The multiton is somewhat an extension of the singleton pattern. It is referred as registry of singletons by the GOF. I don’t know for sure who appointed the name multiton: it’s an analogy derived from the term singleton. So, singleton = single + ton; while multiton = multi + ton.

The singleton pattern guarantees that a class has only one instance; while the multiton allows keeping multiple instances by maintaining a map of related keys and unique objects.  Note that there can be only one instance per key when implementing the multiton pattern. Also, note that the key does not have to be a string value; it can be an object for example. Nonetheless, in our code sniped we will consider the key to be a string.

I am going to tweak my singleton class implementation so that I can make it a multiton instead:

unit Multiton;

interface

uses
  Generics.Collections;

type
  TMultiton = class
  private
    //Private fields and methods here...

     class var _registry: TDictionary<string, TMultiton>;
  protected

  public
    class function Create(aName: string): TMultiton;
    class destructor Destroy;
    class function Lookup(aName: string): TMultiton;
  
    destructor Destroy; override;

    //Other public methods and properties here...  
  end;

implementation

{ TMultiton }

class function TMultiton.Create(aName: string): TMultiton;
begin
  if not Assigned(_registry) then
    _registry:= TDictionary<string, TMultiton>.Create;

  if not _registry.TryGetValue(aName, Result) then
  begin
    Result:= inherited Create as Self;
    _registry.Add(aName, Result);
  end;
end;

class destructor TMultiton.Destroy;
begin
   if Assigned(_registry) then
   begin
     _registry.Values.ToArray[0].Free;     
   end;
end;

class function TMultiton.Lookup(aName: string): TMultiton;
begin
  if Assigned(_registry) then
    _registry.TryGetValue(aName, Result);
end;

destructor TMultiton.Destroy;
var
  _instance: TMultiton;
  ValuesArray: TArray<TMultiton>;         
begin
  if Assigned(_registry) then
  begin
    ValuesArray:= _registry.Values.ToArray;

    _registry.Clear;
    _registry.Free;
    _registry:= nil;

    for _instance in  ValuesArray do
      if _instance <> Self then
        _instance.Free;
  end;

  inherited;
end;

end.

A few things I want you to note:

• Instead of a single instance, we are holding a registry of instances. We do so by introducing the class variable _registry of type TDictionary<string, TMultiton>.  
• We register (create) the different instances by calling the class function Create. This function gets the key name as a parameter. A new instance is only created if no matches to the key name are found in the dictionary. If a match is found, then the corresponding value is returned from the dictionary data structure.
• The Lookup class function allows retrieving a particular instance by giving its key name. Note that the Create function can also be used for this purpose, but it feels more natural to call Lookup for the searches, and Create for the registration (creation) of instances.
• We have provided a regular destructor that once invoked releases all the memory: not only the current multiton instance, but the whole registry.    
• We have also provided a class destructor in case that we forget to manually release the memory.  

This code was compiled with Delphi XE2, but it should also work for all versions above Delphi 2009. Comments, corrections and suggestions are most welcome.

Consider reading these books about design patterns if you haven’t yet:

CodeProject

Dependency Injection in Delphi: a simple example

I want to give a fairly simple Delphi example that will expose the dependency injection pattern. No framework, no third-party library will be needed here: just plain Delphi code.

I won’t dig into the different forms of dependency injection. I will explain the idea of the pattern as simple as possible.

Instead of giving you bunch of definitions, I will present you with some code. The need to inject a dependency will come naturally. You’ll see:

type

  IDependency = interface

  ['{618030A2-DB17-4532-81D0-D5AA6F73DC66}']

    procedure GetType;

  end;




  TDependencyA = class(TInterfacedObject, IDependency)

  public

    procedure GetType;

  end;




  TDependencyB = class(TInterfacedObject, IDependency)

  public

    procedure GetType;

  end;




 TConsumer = class

  private

    FDependency: IDependency;

  public

    constructor Create(aDependencyClassName: string);

    procedure GetDependencyType;

  end;




implementation







{ TDependencyA }




procedure TDependencyA.GetType;

begin

  WriteLn('Instance of type TDependencyA');

end;




{ TDependencyB }




procedure TDependencyB.GetType;

begin

  WriteLn('Instance of type TDependencyB');

end;




{ TConsumer }




constructor TConsumer.Create(aDependencyClassName: string);

begin

  if aDependencyClassName = 'TDependencyA'  then

    FDependency:= TDependencyA.Create

  else if aDependencyClassName = 'TDependencyB'  then

    FDependency:= TDependencyB.Create;

end;




procedure TConsumer.GetDependencyType;

begin

  if FDependency <> nil then

    FDependency.GetType;

end;

It is a good and recommended practice in OOP to decrease coupling as much as possible. This means that each component (class) should avoid knowing implementation details of the other components (classes).

In our example, the TConsumer class has a dependency of type IDependency. So far so good, since we are abstracting any implementation specifics by using an interface (contract). The problem becomes obvious when you take a look at the constructor of TConsumer.

TConsumer.Create is instantiating the concrete classes TDependencyA   or TDependencyB depending on the string parameter aDependencyClassName. As you can see, the design is not well decupled here, because the consumer class (TConsumer) is hard-coding implementation details about its dependency.  

The question is: can we decuple this design even more? Yes, the dependency injection pattern will do it for us.

It’s now time to refactor our code a little bit. We’ll start by changing the signature of the constructor of the TConsumer class:

constructor TConsumer.Create(aDependency: IDependency);

begin

  FDependency:= aDependency;

end;

Instead of choosing the concrete dependency to instantiate within the constructor, we are now injecting the dependency trough the aDependency parameter. Now the class TConsumer is completely independent of the dependency concrete class.

Ok, ok, but we still need to create the concrete dependency instance somewhere, right? Yes, we do. For that we will create a new class TDependencyInjector whose only purpose is to return the right dependency instance. This class will use reflection in order to create the right instance of IDependency. It will use just a string parameter that contains the dependency class name.

uses

  RTTI,

  Dependencies;




type

  TDependencyInjector =  class

  public

    class function GetDependency(aDependencyClassName: string): IDependency;

  end;




implementation




{ TDependencyInjector }




class function TDependencyInjector.GetDependency(aDependencyClassName: string): IDependency;

var

  RttiContext: TRttiContext;

  RttiType: TRttiInstanceType;

begin

  RttiType := RttiContext.FindType(aDependencyClassName) as TRttiInstanceType;

  if RttiType <> nil then

    Result:= RttiType.GetMethod('Create').Invoke(RttiType.MetaclassType, []).AsInterface as IDependency;

end;

Finally, let's put all the pieces together. Consider this console application that puts all the pieces in place:

program DependencyInjection;




{$APPTYPE CONSOLE}




{$R *.res}




uses

...




var

  SomeConsumerObj: TConsumer;

  Dependency: IDependency;




begin

  Dependency:= TDependencyInjector.GetDependency('Dependencies.TDependencyA');

  //Dependency:= TDependencyInjector.GetDependency('Dependencies.TDependencyB');

  SomeConsumerObj:= TConsumer.Create(Dependency);




  try

    SomeConsumerObj.GetDependencyType;

  finally

    SomeConsumerObj.Free;

  end;




  Readln;

end.

In the code above we get the Dependency instance at runtime by using the TDependencyInjector class. Then we inject that dependency using the constructor of the class  TConsumer. We have got a more decoupled design by using dependency injection. Don't you agree? ;-)

Get the full source code of this example here (written in Delphi XE 2).

CodeProject