Find limit of recursion: Difference between revisions
added RPL
(Add ZIg example with showcase of force-enabling and force-disabling tail-recursion elimination, thus making behaviour consistent in all optimization modes.) |
(added RPL) |
||
| (9 intermediate revisions by 6 users not shown) | |||
Line 524:
ext = Recursion(0)</syntaxhighlight>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
<syntaxhighlight lang="vbnet">10 sub recursion(n)
20 print n
30 recursion(1 + n)
40 end sub
50 recursion(0)
60 end</syntaxhighlight>
==={{header|FreeBASIC}}===
Line 542 ⟶ 551:
Segmentation fault (core dumped)
</pre>
==={{header|Gambas}}===
<syntaxhighlight lang="vbnet">Public Sub Main()
Recursion(0)
End
Sub Recursion(n As Long)
Print n
Recursion(1 + n)
End Sub</syntaxhighlight>
==={{header|GW-BASIC}}===
Line 552 ⟶ 575:
33
Out of memory in 20.</pre>
==={{header|Minimal BASIC}}===
<syntaxhighlight lang="qbasic">10 LET N = 0
20 LET N = N + 1
30 PRINT N
40 GOSUB 20
50 END</syntaxhighlight>
{{out}}
<pre> 257
40: error: stack overflow</pre>
==={{header|MSX Basic}}===
{{works with|MSX BASIC|any}}
The [[#GW_BASIC|GW BASIC]] solution works without any changes.>
==={{header|QBasic}}===
Line 562 ⟶ 599:
ext = Recursion(0)</syntaxhighlight>
==={{header|Quite BASIC}}===
<syntaxhighlight lang="qbasic">10 LET N = 0
20 LET N = N + 1
30 PRINT N
40 GOSUB 20</syntaxhighlight>
==={{header|Sinclair ZX81 BASIC}}===
Line 2,618 ⟶ 2,661:
Obviously, if the procedure '''recursive''' would have contained local variables, the depth of recursion would be reached much earlier...
=={{header|PL/M}}==
<syntaxhighlight lang="PL/M">
100H:
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;
PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT;
PRINT$NUM: PROCEDURE (N);
DECLARE S (8) BYTE INITIAL ('.....',13,10,'$');
DECLARE (N, P) ADDRESS, C BASED P BYTE;
P = .S(5);
DIGIT:
P = P-1;
C = N MOD 10 + '0';
IF (N := N/10) > 0 THEN GO TO DIGIT;
CALL PRINT(P);
END PRINT$NUM;
RECURSE: PROCEDURE;
DECLARE CNT ADDRESS INITIAL (1);
CALL PRINT$NUM(CNT);
CNT = CNT + 1;
CALL RECURSE;
END RECURSE;
CALL RECURSE;
CALL EXIT;
EOF
</syntaxhighlight>
=={{header|PowerShell}}==
Line 2,919 ⟶ 2,994:
recurse(x+1)
</syntaxhighlight>
=={{header|RPL}}==
« 1 + <span style="color:blue">RECUR</span> » '<span style="color:blue">RECUR</span>' STO
0 <span style="color:blue">RECUR</span>
Each recursive call will increase the return stack size by 5 nibbles, which means that on a basic 32-kilobyte calculator, there's room for over 10,000 recursive calls of the above type. If the recursion algorithm needs to pass arguments through the data stack or use local variables, the number of recursions will be much lower.
=={{header|Ruby}}==
Line 3,210 ⟶ 3,291:
recurse 1</syntaxhighlight>
=={{header|Uxntal}}==
Uxn has a known stack size of 256 bytes, which allows 128 function calls. However, assuming we don’t know this, we can find the stack size with a program anyway. In older versions of Uxn, it was possible to detect stack overflow with the System vector, which would make this task easier, but the current Uxn stacks are circular, with no overflow and underflow checks, which means that we have to get a bit more creative. Calling a recursive function enough times will cause the return stack pointer to wrap around and overwrite the first return address, which means execution will be trapped in the recursive function forever. By detecting when the function has run more times than expected, the recursion limit can be found.
<syntaxhighlight lang="Uxntal">|00 @System &vector $2 &expansion $2 &wst $1 &rst $1 &metadata $2 &r $2 &g $2 &b $2 &debug $1 &state $1
|10 @Console &vector $2 &read $1 &pad $4 &type $1 &write $1 &error $1
|00 @calls $1
|0100
#01
&loop
DUP .calls STZ
recurse
INC !&loop
@recurse
( keep calling recurse until stack value is 00 )
#01 SUB DUP #00 EQU ?&done
recurse
( as we walk back up the stack, increment counter )
&done INC
( if we go above the original call count, the stack was corrupted )
DUP .calls LDZ GTH ?&fail
JMP2r
&fail
;msg1 print-str
.calls LDZ print-hex
;msg2 print-str
#80 .System/state DEO BRK
@print-str
&loop
LDAk .Console/write DEO
INC2 LDAk ?&loop
POP2
JMP2r
@print-hex
DUP #04 SFT print-digit #0f AND print-digit
JMP2r
@print-digit
DUP #09 GTH #27 MUL ADD #30 ADD .Console/write DEO
JMP2r
@msg1 "Stack 20 "overflow 20 "at 20 "# 00
@msg2 20 "calls. 0a00</syntaxhighlight>
=={{header|Vala}}==
Line 3,316 ⟶ 3,449:
prompt$ echo $?
11</pre>
=={{header|Wren}}==
I cannot find any published information on the maximum amount of memory that can be used by a fiber's stack - and hence the limit of recursion for a given function - but it appears to be 4 GB on a sufficiently large 64-bit system such as my own (32 GB) with no shell limit.
The final figure produced by the following script was 536,870,500 and multiplying by 8 (the number of bytes of storage required for the parameter 'n') gives 4,294,964,000 which is just 3,296 bytes short of 4 GB.
In Wren a fiber's stack starts small and is increased as required. It appears that the runtime makes no attempt to check for any limitation internally leaving the script to eventually segfault.
<syntaxhighlight lang="wren">var F = Fn.new { |n|
if (n%500 == 0) System.print(n) // print progress after every 500 calls
F.call(n + 1)
}
F.call(1)</syntaxhighlight>
{{out}}
<pre>
...
536870000
536870500
Segmentation fault (core dumped)
</pre>
=={{header|x86 Assembly}}==
Line 3,337 ⟶ 3,490:
I've used gdb and the command <tt>print $eax</tt> to know when the segmentation fault occurred. The result was 2094783.
=={{header|
On the Raspberry Pi this causes a Segmentation fault at the recursion
levels shown in Output.
The stack size is about 8 MB. The original compiler pushes a single
4-byte value (the return address for Recurse) onto the stack.
The optimizing compiler pushes an additional 4-byte value (r11), which is
the base address of variables local to Recurse. But since there aren't
any local variables in this situation, the optimizing compiler isn't as
optimal as it could be.
The MS-DOS version crashes at 12,224 levels. The allocated stack size is
16,384 bytes. But since each call pushes a 4-byte value, the actual limit
should be a maximum of 4,096.
<syntaxhighlight lang "XPL0">int Lev;
proc Recurse;
[if (Lev & $3FF) = 0 then
[IntOut(0, Lev); ChOut(0, ^ )];
Lev:= Lev+1;
Recurse;
];
[Lev:= 0;
Recurse;
]</syntaxhighlight>
{{out}}
<pre>
2,096,128 for the original compiler (xplr)
1,047,552 for the optimizing compiler (xpl0)
</pre>
Line 3,391 ⟶ 3,555:
{{Trans|C}}
'''Works with:''' 0.11.x, 0.12.0-dev.1381+61861ef39
For 0.10.x, replace @call(.some_call_modifier, ...) with @call(.{ .modifier = .some_call_modifier }, ...) in these examples.
===Leave TRE to the compiler===
In this version, Zig compiler is free to (not) optimize recursive function, so behaviour may change from one optimization mode to another, like it was with 2-nd example from C section.
<syntaxhighlight lang="zig">const std = @import("std");
fn recurse(i: c_uint) void {
std.debug.print("{d}\n", .{i});
// We use wrapping addition operator here to mirror C behaviour.
recurse(i +% 1);
// Line above is equivalent to:
// @call(.auto, recurse, .{i +% 1});
}
pub fn main() void {
recurse(0);
return;
}</syntaxhighlight>
===Force-disable TRE===
To force-disable "simple tail recursion elimination" (STRE) for all optimize modes, we can use "never_tail" field of enum "std.builtin.CallModifier". It works not as hint, but as a hard requirement, so if it's impossible to fulfill, compile error is outputted.
<syntaxhighlight lang="zig">const std = @import("std");
Line 3,410 ⟶ 3,593:
Segmentation fault occurs at different values of "i", depending on running platform, but on my platform (with stack size reported by ulimit as 16384) both C and Zig versions (compiled without optimizations output last value in approximately [523500, 524000] range.
gcc compiler with -O2 flag eliminated tail recursion, as mentioned in
===Force-enable TRE===
Similarly, we can force-enable mentioned optimization in all optimize modes by using enum field "always_tail". It's (again) a hard requirement and will emit compile error if this requirement is impossible to complete.
<syntaxhighlight lang="zig">const std = @import("std");
| |||