[fpc-pascal] fpc isn't optimised for tail recursion, is it?
Steve Litt
slitt at troubleshooters.com
Mon Jun 12 03:44:19 CEST 2023
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?
Thanks,
SteveT
Steve Litt
Autumn 2022 featured book: Thriving in Tough Times
http://www.troubleshooters.com/bookstore/thrive.htm
More information about the fpc-pascal
mailing list