Factorial using trampolines

Question

I've translated this Java code into Delphi code:

unit Trampoline;

interface

type
  ITrampoline<T> = interface
    function Get: T;
    function Run: ITrampoline<T>;
    function Execute: T;
  end;

  TTrampoline<T> = class(TInterfacedObject, ITrampoline<T>)
  public
    function Get: T; virtual;
    function Run: ITrampoline<T>; virtual;
    function Execute: T; virtual; final;
  end;

  TFactorial = class(TTrampoline<integer>)
  private
    fsum, fn: integer;
  public
    constructor Create(n, sum: integer);
    class function Factorial(n, sum: integer): ITrampoline<Integer>; static;
    function run: ITrampoline<Integer>; override;
  end;

implementation

uses System.Generics.Defaults;

function TTrampoline<T>.Run: ITrampoline<T>;
begin
  Result:= nil;
end;

function TTrampoline<T>.Get: T;
begin
  Result:= default (T);
end;

function TTrampoline<T>.Execute: T;
var
  Comparer: IEqualityComparer<T>;
  Trampoline: ITrampoline<T>;
begin
  Trampoline:= Self;
  Comparer:= TEqualityComparer<T>.Default;
  while Comparer.Equals(Trampoline.get, default (T)) do begin
    Trampoline:= Trampoline.run;
  end;
  Result:= Trampoline.get;
end;

type
  TDoneFactorial = class(TFactorial)
    function get: integer; override;
  end;

constructor TFactorial.Create(n, sum: integer);
begin
  fn:= n;
  fsum:= sum;
end;

class function TFactorial.Factorial(n, sum: integer): ITrampoline<Integer>;
begin
  if (n <= 1) then begin
    Result:= TDoneFactorial.Create(n, sum);
  end else begin
    Result:= TFactorial.Create(n, sum);
  end;
end;

function TDoneFactorial.get: integer;
begin
  Result:= fsum;
end;

function TFactorial.run: ITrampoline<Integer>;
begin
  Result:= Factorial(fn - 1, fsum * fn);
end;

end.

Usage:

procedure TForm5.Button1Click(Sender: TObject);
var
  Outcome: Integer;
begin
  Outcome:= TFactorial.Factorial(StrToInt(Edit1.Text), 1).Execute;
  Label2.Caption:= IntToStr(OutCome);
end;

It runs nicely, in all the iterations of the execute method the stack pointer does not move and hence it will not generate a stack overflow no matter how many deep the recursion goes.

It is rather inefficient though because of:

• The implicit try - finally guarding the interface variable
• The constant creation of new structures on the heap.

Is there a more efficient way to do this?

Never mind the fact that factorials are a stupid example for recursion. I know recursion is only really useful with trees.

Answer 1

Recursion can make for elegant code, but it can also make for very slow code. Calculating Fibonacci numbers and Factorials are both classic examples where the recursive algorithm is simple to implement, but slow beyond the first few (and very small) input values.

I don't know Delphi, so I quickly implemented this in VB6, but you should be able to consider it psuedo-code.

Function Factorial(x As Integer) As Long
    Dim result As Long
    Dim startIndex As Integer

    result = 1
    For startIndex = x To 1 Step -1
        result = result * startIndex
    Next

    Factorial = result
End Function