Find limit of recursion: Difference between revisions
added RPL
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(added RPL) |
||
| (15 intermediate revisions by 9 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 1,125 ⟶ 1,168:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
proc recurse i . .
print i
.
recurse i + 1
.
</syntaxhighlight>
<pre>
.
.
9100
InternalError: too much recursion
</pre>
Line 2,416 ⟶ 2,460:
depth: 3725849 (tearing down)
</pre>
=={{header|Phixmonti}}==
<syntaxhighlight lang="Phixmonti">/# Rosetta Code problem: http://rosettacode.org/wiki/Find_limit_of_recursion
by Galileo, 10/2022 #/
def sec msec int enddef
sec var t
def recursion
1 +
sec t 1 + > if t 1 + var t dup print nl endif
recursion
enddef
0 recursion</syntaxhighlight>
{{out}}
<pre>281007
431296
581394
730334
879369
1029498
1179530
1330012
1479943
1630421
1781000
1930959
2081595
2231553
2381764
2531888
2682392
2832907
2983242
3133677
3284111
3434178
3584534
3734997
3885133
4035703
4185613
4336355
4486693
4635764
4786107
4935949
5086156
5235687
5385416
5535747
5685633
5835858
5985753
6135743
6285747
6436123
6585421
6735203
6885286
7035236
7185132
7334455
7484643
7618401
7731876
7852957
7976679
8103526
8230876
8358600
8488773
8623796
8763058
8898198
9046186
9189766
9339550
9489755
9633985
9781880
9931149
10080277
10227093
10361576
10498033
10646428
10795650
10940499
11090442
11239675
11389776
11539185
11687704
11831276
11966704
12086836
Your program has run out of memory, one moment please
Global & Local Variables
*** Error detected ***
*** Stack content:
[12197563]
*** Location: .. Rosetta Code problem: http://rosettacode.org/wiki/Find_limit_of_recursion by Galileo, 10/2022 #/ def sec msec ..
=== Press any key to exit ===</pre>
=={{header|PHP}}==
Line 2,507 ⟶ 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,808 ⟶ 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,099 ⟶ 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,184 ⟶ 3,428:
[Level 1719] no good</pre>
=={{header|V (Vlang)}}==
It'll be some number, depending on machine and environment.
<syntaxhighlight lang="go">// Find limit of recursion, in V (Vlang)
module main
Line 3,205 ⟶ 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,226 ⟶ 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,276 ⟶ 3,551:
* The <code>CP</code> instruction only compares the accumulator to an 8 bit register, so to compare HL to BC we actually have to subtract them. If the result is zero, they were the same to begin with.
* If they're different, then the act of pushing AF clobbered the stack pointer we backed up in step 1. This means recursion is at its limit, so quit looping and halt the CPU.
=={{header|Zig}}==
{{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");
fn recurse(i: c_uint) void {
std.debug.print("{d}\n", .{i});
// We use wrapping addition operator here to mirror C behaviour.
@call(.never_tail, recurse, .{i +% 1});
}
pub fn main() void {
recurse(0);
return;
}</syntaxhighlight>
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 2-nd example from C section, but in this Zig example recurse function is never turned into loop, even when enabling different optimization modes — we explicitly prohibited compiler from doing it in any optimize/build mode!
===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");
fn recurse(i: c_uint) void {
std.debug.print("{d}\n", .{i});
// We use wrapping addition operator here to mirror C behaviour.
@call(.always_tail, recurse, .{i +% 1});
}
pub fn main() void {
recurse(0);
return;
}</syntaxhighlight>
On my machine, segmentation fault never occurs, instead resulting in infinite loop in all optimize modes (as intended).
=={{header|zkl}}==
| |||