Anonymous user
Find limit of recursion: Difference between revisions
Initial implementation.
m (Added the Sidef language) |
(Initial implementation.) |
||
Line 51:
<pre>
Recursion depth on this system is 524091
</pre>
=={{header|ALGOL 68}}==
This is a mind-bogglingly silly task. The depth of recursion in Algol 68 proper is unlimited. Particular implementations will reach a limit, if only through exhaustion of storage and/or address space and/or time before power failure. If not time limited, the depth reached depends very much on what the recursive routine needs to store on the stack, including local variables if any. The simplest recursive Algol68 program is:
<lang algol68>PROC recurse = VOID : recurse; recurse</lang>
For what it's worth this one-liner running under Algol68 Genie and 64-bit Linux reaches a depth of 3535 with the shell's default stack size of 8Mbytes and 28672 when set to 64Mbytes,
as shown by the following output. From this we can deduce that Genie does not implement tail recursion. The --trace option to a68g prints a stack trace when the program crashes; the first two commands indicate the format of the trace, the third counts the depth of recursion with the default stack size and the fourth shows the result of quadrupling the size of the stack.
{{Out}}
<pre>
pcl@anubis ~/a68/Rosetta $ a68g --trace Recurse.a68 | head
genie: frame stack 6144k, expression stack 2048k, heap 49152k, handles 8192k
BEGIN MODE DOUBLE = LONG REAL, QUAD = LONG LONG REAL;
-
1 PROC recurse = VOID : recurse; recurse
-
genie_unit
1 PROC recurse = VOID : recurse; recurse
-
genie_unit
1 PROC recurse = VOID : recurse; recurse
pcl@anubis ~/a68/Rosetta $ a68g --trace Recurse.a68 | tail
1 PROC recurse = VOID : recurse; recurse
-
genie_unit
1 PROC recurse = VOID : recurse; recurse
-
genie_unit
1 PROC recurse = VOID : recurse; recurse
1
a68g: runtime error: 1: stack overflow (detected in particular-program).
Genie finished in 0.19 seconds
pcl@anubis ~/a68/Rosetta $ a68g --trace Recurse.a68 | grep recurse | wc
3535 28280 159075
pcl@anubis ~/a68/Rosetta $ prlimit --stack=67108864 a68g --trace Recurse.a68 | grep recurse | wc
28672 229376 1290240
pcl@anubis ~/a68/Rosetta $
</pre>
| |||