8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – xmojmr Jul 26 '14 at 19:11
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.