[fpc-pascal] Recursion optimization by compiler

[José Mejuto]

Hello FPC-Pascal,

Friday, September 3, 2010, 1:12:31 PM, you wrote:

BA> After my previous post, "TreeView and Nonrecursion", I'd tried to ask the same
BA> topics in stackoverflow.com 
BA> (http://stackoverflow.com/questions/3630047/treeview-control-and-nonrecursion)
BA> and I got something new.
BA> It is possible to recurse without using up the stack space.  Optimizing
BA> compilers are able to accomplish certain types of recursion into  efficient
BA> non-recursive loops, but the code has to be written into a tail recursion form.
BA> Is there such a recursion optimization in FPC? If it is not enabled by default,
BA> how to enable it?

That kind of "optimization" to me only seems interesting in two
possible situations, when calling functions is high costly or when
there is a very limited stack amount (really, really small). From my
point of view if you need more that 1MB of stack size I'm quite sure
that you are doing something wrong, because around 65000 recursion
levels looks not very good.

The recursion "optimization" is being done using regular RAM as a
stack:

function Recursive(var a: integer): boolean;
begin
  if a=1000 then begin
    Result:=false;
    exit;
  end else begin
    inc(a);
    Result:=Recursive(a);
  end;
end;

Function Iterative(var a: integer): boolean;
var
  Stack: TStack;
  v: integer;
begin
  stack.Push(a);
  while true do begin
    v:=stack.pop;
    if v=1000 then begin
      Result:=true;
      a:=v;
      break;
    end else begin
      inc(v);
      Stack.push(v);
    end;
  end;
  stack.free;
end;

To me the first one looks more clear...

-- 
Best regards,
 José