# Factorial using trampolines

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.

• your code problem is attractive:=0 for me. Why would I spend any time and thinking on a factorial problem. What do you really need to solve, use, what is your real-life application? If you are just interested in the factorial problem then search (Google) for "tail call optimization factorial" and you'll find many examples of factorial code in various languages. Converting recursion into simple loop is THE way, tail recursion is the pattern that compilers use to detect and implement the transformation Jul 26, 2014 at 19:11

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