[fpc-pascal] fpc isn't optimised for tail recursion, is it?

[Nikolay Nikolov]

On 6/12/23 04:44, Steve Litt via fpc-pascal wrote:
> Hi all,
>
> Tail recursion is recursion in which absolutely nothing gets executed
> after the return statement. Some programming languages, including
> Guile, optimize for tail recursion such that tail recursive algorithms
> don't use additional stack space as you pile up more and more levels of
> recursion.
>
> I did a typical non-tail recursion hello world program, and if I set
> the "now-go-backward" number high enough, it segfaulted, I assume
> because I ran it out of stack space with so many levels of recursion.
>
> So, to see if FPC is optimized for tail recursion, I tested it with the
> following program, which I think is tail-recursive.
>
> ===========================================================
> program recursion_hello;
>
> function nextt(num: int64): int64;
>     begin
>     writeln('Going deeper=>   ', num);
>     if (num > 0) then
>        begin
>        nextt(num - 1);
>        end;
>     nextt := num;
>     end;
>
> begin
>    nextt(1000000000);
> end.
> ===========================================================
>
> As you can see, the return from function occurs at the very end of
> function nextt(), which I believes makes my algorithm tail-recursive.
> Running my program, I found it segfaulted pretty much the same as the
> non-tail-recursive version.
>
> I tried to look up all relevant compiler directives, finding {s-}
> and {$stackspaces off}, which requires no local vars and no parameters
> to not implement a stackspace for a fuunction. So I made the
> "now-go-backward" number a global, and made the recursive function a
> procedure, and still, I got the segfaulting.
>
> So, subject to your guidance, I'm assuming FPC isn't optimized for tail
> recursion. Is my assumption an accurate one?

FPC supports tail recursion optimization, it is enabled at -O2 
optimization level for most CPUs, however your code isn't eligible for 
that optimization, because there's extra code, after the recursive 
invoke. If you change it like that:

program recursion_hello;

function nextt(num: int64): int64;
    begin
    writeln('Going deeper=>   ', num);
    nextt := num;
    if (num > 0) then
       begin
       nextt(num - 1);
       end;
    end;

begin
   nextt(1000000000);
end.

And if you compile with -O2 it works, without segfaulting (tested with 
FPC 3.2.2 on x86_64-linux).

Nikolay

>
> Thanks,
>
> SteveT
>
> Steve Litt
> Autumn 2022 featured book: Thriving in Tough Times
> http://www.troubleshooters.com/bookstore/thrive.htm
> _______________________________________________
> fpc-pascal maillist  -  fpc-pascal at lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal