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

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

On 12-6-2023 08:15, Nikolay Nikolov via fpc-pascal wrote:

Shouldn't the recursive call assign the result?

nextt(num - 1);

nextt:=nextt(num - 1);

if you don't use the result, the whole call may be optimized away?

According to you other posts, I won't be surprised that you think in a C/C++ way.
This doesn't change anything in your last example, but particularly  :

nextt := num;

doesn't behave like in C :

return num;

In pascal I think the equivalent would be :

nextt := num; exit;

Jean SUZINEAU via fpc-pascal said on Mon, 12 Jun 2023 18:04:07 +0200

According to you other posts, I won't be surprised that you think in a C/C++ way.

:-) Busted! I used Pascal 1984-1993, and C 1986-present with C++ (hate it) 1990-1998. So I long ago forgot the details of pascal, and program pretty much every language with a C accent.

Busted again. I was thinking that nextt := num not only defined the return value, but actually executed the return. Because that's how the return statement works in C. I now know (remember actually) that the assignment doesn't trigger the return.

Thanks,

SteveT

Marco van de Voort via fpc-pascal said on Mon, 12 Jun 2023 09:12:22 +0200

Thanks Marco,

You're right, of course. I'm not using my function return. That being said, as far as I know, FPC can't optimize for tail recursion if I do use the function return in any way. So I didn't use the function return.

Of course, you bring up a point of cleanness and style. If I don't use the function return, I should have made it a procedure instead of a function.

Anyway, I learned from my forays into Guile that I don't yet have a good mental model of functional programming, hence my confusion.

Thanks,

SteveT

Steve Litt
Autumn 2022 featured book: Thriving in Tough Times http://www.troubleshooters.com/bookstore/thrive.htm

Nikolay Nikolov via fpc-pascal said on Mon, 12 Jun 2023 09:15:17 +0300

On 6/12/23 04:44, Steve Litt via fpc-pascal wrote:

[snip]

Thanks Nickolay,

You're right about not assigning nextt below the call to nextt, and about the -O2 argument. After learning from you about -O2 and investigating further, I used {$OPTIMIZE tailrec}, which isn't quite the same thing, but it worked beautifully. {$OPTIMIZE on} also enables tail recursion and speeds things up about 10% of tailrec.

Thanks for your help.

SteveT

Steve Litt
Autumn 2022 featured book: Thriving in Tough Times http://www.troubleshooters.com/bookstore/thrive.htm

Steve,

If you're looking for equivalent to "return X", use "Exit" with a parameter in Pascal: "Exit(X)".

It's just a shortcut for "Result := X; Exit;"

Regards,
Michalis

pon., 12 cze 2023 o 19:57 Steve Litt via fpc-pascal napisał(a):

Le 12/06/2023 à 19:05, Steve Litt via fpc-pascal a écrit :

Busted! I used Pascal 1984-1993

So I guess you are not familiar too with the "Result" variable which appeared with Delphi 1 in 1995 if I remember correctly.

nextt:= num;

can be written to as :

Result:= num;

https://www.freepascal.org/docs-html/ref/refse94.html

I prefer Result because it reduces risks of confusion with recursive call and you can eventually take the address of Result with @Result (where @nextt would take the address of the function nextt), pass it by reference to another function ( e.g. FillChar( Result, SizeOf(Result), 0); ) ,
it behaves like a normal variable.