Limit of Recursion (Rosetta Code task); interesting MacOS (M1) observation

General
1

Hi;

I recently re-examined the Ada version of the Rosetta Code task “Find limit of recursion”.

What is supposed to happen is Ada catching the problem before the OS does, but in my case, the execution of the Ada executable was killed.

./test_it.bash: line 7: 14003 Killed: 9 ./test_recursion_depth

When I modified the code so that each recursive call would print the current depth, the modified Ada executeable was able to run to completion.

I inserted the following line prior to line number 6:

Put_Line ("DEBUG: " & Integer’Image (Depth));

…

DEBUG: 29045
DEBUG: 29046
Recursion depth on this system is 29046

BTW, it seems that the three leading and terminating backslashes method of formatting code is wonky today…

Anyway, I thought that this was interesting…

RBE

2

Nope, it is the OS that detects the problem, obviously. So the behaviour depends on the OS and the machine architecture. The code works perfectly well under x86 Linux and Windows.

The task comment explains the circumstances under which Storage_Error can be handled.

When you call Put_Line you require much more stack than when upon a recursive call. Thus as Put_Line fails you have more stack available to return without killing the process.

So the task failure is to be attributed either to BSD (Mac OS) or to ARM. I leave the investigation up to you.

You could replace Put_Line with something like this:

with Ada.Text_IO;  use Ada.Text_IO;

procedure Test is
   function Recursion (Depth : Positive) return Positive is
   begin
      declare
         Garbage : String (1..80); -- Reduce the number until it fails
      begin
         return Recursion (Depth + 1);
      end;
   exception
      when Storage_Error =>
         return Depth;
   end Recursion;
begin
   Put_Line ("Recursion depth on this system is" & Integer'Image (Recursion (1)));
end Test;
3

Note that with GNAT, you have to add the option -fstack-checkto get the Ada behavior of raising Storage_Error on stack overflow.

1 Like