Find limit of recursion: Difference between revisions
m
syntax highlighting fixup automation
Puppydrum64 (talk | contribs) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 13:
Reading the current stack pointer is unreliable, as there is no requirement that the stack be "aligned" in any way. Unlike the 8086 and Z80, which require all pushes/pops to be exactly two bytes, the 6502's stack will likely contain both 1 byte registers and 2 byte return addresses. It's much easier to use a stack canary. Pick a value that is unlikely to be used in your program.
<
lda #$BE
sta $0100
Line 27:
lda $0100 ;if this no longer equals $BE the stack has overflowed
cmp #$BE
bne StackHasOverflowed</
=={{header|8080 Assembly}}==
Line 51:
at run-time, at the cost of some overhead per call.
<
lxi b,0 ; BC holds the amount of calls
call recur ; Call the recursive routine
Line 99:
;;; If the guard is overwritten, the stack has overflowed.
GUARD: equ $+2 ; Make sure it is not a valid return address
guard: dw GUARD</
{{out}}
Line 120:
of calls you can make before the stack is full (and would overwrite your program).
<
lxi h,-top ; Subtract highest used location from stack pointer
dad sp
Line 159:
;;; This means anything from this place up to SP is free for the
;;; stack.
top: equ $ </
{{out}}
Line 166:
=={{header|ACL2}}==
<
(if (zp x)
0
(prog2$ (cw "~x0~%" x)
(1+ (recursion-limit (1+ x))))))</
{{out}} (trimmed):
Line 187:
=={{header|Ada}}==
<
procedure Test_Recursion_Depth is
Line 199:
begin
Put_Line ("Recursion depth on this system is" & Integer'Image (Recursion (1)));
end Test_Recursion_Depth;</
Note that unlike some solutions in other languages this one does not crash (though usefulness of this task is doubtful).
Line 218:
=={{header|ALGOL 68}}==
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:
<
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 octupling the size of the stack.
Line 255:
===Test 1===
A basic test for Applescript, which has a notoriously shallow recursion stack.
<
on recursionDepth()
script go
Line 274:
recursionDepth()
end run</
{{Out}}
<pre>"Recursion limit encountered at 502"</pre>
Line 280:
===Test 2===
We get a fractionally higher (and arguably purer) result by deriving the highest Church Numeral (Church-encoded integer) that can be represented using AppleScript:
<
-- (This should be a good proxy for recursion depth)
Line 373:
on succ(x)
1 + x
end succ</
{{Out}}
<pre>"The highest Church-encoded integer representable in Applescript is 571"</pre>
Line 384:
Testing with no local variables and with an external 'try' statement, the maximum recursion depth possible appears to be 733. (732 if the code below's run as an applet instead of in an editor or from the system script menu.) So, depending on what a script actually does, the limit can be anything between <502 and 733. In practice, it's very difficult for well written AppleScript code to run out of stack.
<
on recursion()
Line 399:
-- display dialog result -- Uncomment to see the result if running as an applet.
end try
end run</
{{output}}
<
=={{header|Arturo}}==
<
print x
recurse x+1
]
recurse 0</
{{out}}
Line 425:
=={{header|AutoHotkey}}==
<
Recurse(x)
Line 431:
TrayTip, Number, %x%
Recurse(x+1)
}</
Last visible number is 827.
=={{header|AutoIt}}==
<
$depth=0
recurse($depth)
Line 442:
ConsoleWrite($depth&@CRLF)
Return recurse($depth+1)
EndFunc</
Last value of $depth is 5099 before error.
Error: Recursion level has been exceeded - AutoIt will quit to prevent stack overflow.
=={{header|AWK}}==
<
#
# version depth messages
Line 468:
if (n > 999999) { return }
x()
}</
=={{header|Axe}}==
Line 475:
In Axe 1.2.2 on a TI-84 Plus Silver Edition, the last line this prints before hanging is 12520. This should be independent of any arguments passed since they are not stored on the stack.
<
Lbl RECURSE
.Optionally, limit the number of times the argument is printed
Disp r₁▶Dec,i
RECURSE(r₁+1)</
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
Each GOSUB consumes 6 bytes of stack space and when more than 25 levels have been reached and an <code>?OUT OF MEMORY ERROR</code> message is displayed.
<
110 PRINT D" ";
120 LET D = D + 1
130 GOSUB 110"RECURSION</
{{out}}
<pre>RECURSION DEPTH
Line 496:
Utterly dependent on the stack size and RAM available to the process.
<
FUNCTION recurse(i)
PRINT i
Line 503:
END FUNCTION
extraneous = recurse(0)</
{{out}}
Line 517:
==={{header|BASIC256}}===
<
print i
ext = Recursion(i + 1)
Line 523:
end function
ext = Recursion(0)</
==={{header|FreeBASIC}}===
<
print n
sisyphus( 1 + n )
end sub
sisyphus(0)</
{{out}}
<pre>
Line 544:
==={{header|GW-BASIC}}===
<
20 N# = N# + 1
30 LOCATE 1,1:PRINT N#
40 GOSUB 20</
{{out}}
<pre>
Line 555:
==={{header|QBasic}}===
{{works with|QBasic|1.1}}
<
PRINT i
ext = Recursion(i + 1)
Line 561:
END FUNCTION
ext = Recursion(0)</
==={{header|Sinclair ZX81 BASIC}}===
The only limit is the available memory.
<
20 GOSUB 30
30 PRINT AT 0,0;D
40 LET D=D+1
50 GOSUB 30</
{{out}}
Run with 1k of RAM:
Line 578:
==={{header|Tiny BASIC}}===
<
20 LET M = 0
30 LET N = N + 1
Line 584:
50 IF N = 32767 THEN PRINT M," x 2^16"
60 IF N = 32767 THEN LET N = -N
70 GOSUB 30</
{{out}}
<pre>1 x 2^16
Line 600:
{{works with|BASIC256}}
{{works with|QBasic}}
<
PRINT i
LET ext = Recursion(i + 1)
Line 607:
LET ext = Recursion(0)
END</
==={{header|XBasic}}===
{{works with|Windows XBasic}}
<
DECLARE FUNCTION Entry ()
Line 625:
END FUNCTION
END PROGRAM</
==={{header|Yabasic}}===
<
print i
Recursion(i + 1)
end sub
Recursion(0)</
==={{header|ZX Spectrum Basic}}===
On the ZX Spectrum recursion is limited only by stack space. The program eventually fails, because the stack is so full that there is no stack space left to make the addition at line 110:
<
100 PRINT AT 1,1; "Recursion depth: ";d
110 LET d=d+1
120 GO SUB 100: REM recursion
130 RETURN: REM this is never reached
200 STOP</
{{out}}(from a 48k Spectrum):
<pre> Recursion depth: 13792
Line 650:
MUNG.CMD is a commandline tool written in DOS Batch language. It finds the limit of recursion possible using CMD /C.
<
set /a c=c+1
echo [Depth %c%] Mung until no good
cmd /c mung.cmd
echo [Depth %c%] No good
set /a c=c-1</
Result (abbreviated):
Line 672:
If one uses <code>call</code> rather than <code>CMD/C</code>, the call depth is much deeper but ends abruptly and can't be trapped.
<
set /a c=c+1
echo [Depth %c%] Mung until no good
call mung.cmd
echo [Depth %c%] No good
set /a c=c-1</
Result (abbreviated):
Line 691:
You also get the exact same results when calling mung internally, as below
<
set c=0
:mung
Line 698:
call :mung
set /a c=c-1
echo [Level %c%] No good</
Setting a limit on the recursion depth can be done like this:
<
set c=0
:mung
Line 710:
call :mung %c%
set /a c=%1-1
echo [Level %c%] No good</
=={{header|BBC BASIC}}==
<
END
Line 719:
IF depth% MOD 100 = 0 PRINT TAB(0,0) depth%;
PROCrecurse(depth% + 1)
ENDPROC</
{{out}} from BBC BASIC for Windows with default value of HIMEM:
<pre>
Line 732:
Most interpreters allocate their stack on the global heap, so the size of the stack will depend on available memory, and on a modern system you're likely to run out of patience long before you run out of memory. That said, there have been some interpreters with a fixed stack depth - as low as 199 even - but that isn't a common implementation choice.
<
=={{header|BQN}}==
Tested with the [[CBQN]] REPL on Ubuntu Linux.
<
0
1
Line 746:
Error: Stack overflow
at {𝕊1+•Show 𝕩}0
</syntaxhighlight>
=={{header|Bracmat}}==
<
Observed recursion depths:
Line 757:
=={{header|C}}==
<
void recurse(unsigned int i)
Line 769:
recurse(0);
return 0;
}</
Segmentation fault occurs when i is 523756.
Line 780:
The following code may have some effect unexpected by the unwary:
<
char * base;
Line 802:
recur();
return 0;
}</
With GCC 4.5, if compiled without -O2, it segfaults quickly; if <code>gcc -O2</code>, crash never happens, because the optimizer noticed the tail recursion in recur() and turned it into a loop!
=={{header|C sharp|C#}}==
<
class RecursionLimit
{
Line 819:
Recur(i + 1);
}
}</
Through debugging, the highest I achieve is 14250.
Line 826:
=={{header|C++}}==
<
#include <iostream>
Line 839:
recurse(0);
}
</syntaxhighlight>
=={{header|Clojure}}==
<
=> (def *stack* 0)
=> ((fn overflow [] ((def *stack* (inc *stack*))(overflow))))
Line 848:
=> *stack*
10498
</syntaxhighlight>
=={{header|COBOL}}==
{{works with|OpenCOBOL}}
<
program-id. recurse.
data division.
Line 901:
*> room for a better-than-abrupt death here.
exit program.</
Compiled with <pre>cobc -free -x -g recurse.cbl</pre> gives, after a while,
<pre>...
Line 933:
{{works with|OpenCOBOL}}
<
PROGRAM-ID. recurse RECURSIVE.
DATA DIVISION.
Line 957:
EXIT PROGRAM.
END PROGRAM recurse-sub.
END PROGRAM recurse. </
Compiled with <pre>cobc -x -g recurse.cbl</pre> gives
Line 971:
=={{header|CoffeeScript}}==
<
recurse = ( depth = 0 ) ->
try
Line 979:
console.log "Recursion depth on this system is #{ do recurse }"
</syntaxhighlight>
{{out}} Example on [http://nodejs.org Node.js]:
Line 988:
=={{header|Common Lisp}}==
<
(defun recurse () (recurse))
(trace recurse)
(recurse)
</syntaxhighlight>
{{out}} This test was done with clisp under cygwin:
Line 1,008:
=={{header|Crystal}}==
<
puts counter
recurse(counter + 1)
Line 1,014:
recurse()
</syntaxhighlight>
{{out}}
Line 1,023:
=={{header|D}}==
<
void recurse(in uint i=0) {
Line 1,032:
void main() {
recurse();
}</
With the DMD compiler, using default compilation arguments, the stack overflows at 51_002.
Line 1,041:
=={{header|Dc}}==
Tail recursion is optimized into iteration by GNU dc, so I designed a not tail recursive function, summing all numbers up to n:
<
[q]sg
[dSn d1[>g 1- lfx]x Ln+]sf
Line 1,047:
65400 lhx
65600 lhx</
With the standard Ubuntu stack size limit 8MB I get
{{out}}
Line 1,064:
=={{header|Delphi}}==
{{works with|Delphi|2010 (and probably all other versions)}}
<
{$APPTYPE CONSOLE}
uses
Line 1,084:
Writeln('Press any key to Exit');
Readln;
end.</
{{out}}
Line 1,093:
Recursion limit is a parameter of script execution, which can be specified independently from the stack size to limit execution complexity.
<
procedure Recursive;
Line 1,106:
Recursive;
Println('Recursion Level is ' + IntToStr(level));</
=={{header|Déjà Vu}}==
{{untested|Déjà Vu}}
<
!. n
rec-fun ++ n
rec-fun 0</
This continues until the memory is full, so I didn't wait for it to finish.
Currently, it should to to almost 3 million levels of recursion on a machine with 1 GB free.
Line 1,125:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">func recurse i . .
print i
call recurse i + 1
.
call recurse 0</
<pre>
0
Line 1,144:
=={{header|Emacs Lisp}}==
<
(my-recurse (1+ n)))
(my-recurse 1)
=>
enters debugger at (my-recurse 595),
per the default max-lisp-eval-depth 600 in Emacs 24.1</
Variable <code>max-lisp-eval-depth</code>[http://www.gnu.org/software/emacs/manual/html_node/elisp/Eval.html#index-max_002dlisp_002deval_002ddepth-539] is the maximum depth of function calls and variable <code>max-specpdl-size</code>[http://www.gnu.org/software/emacs/manual/html_node/elisp/Local-Variables.html#index-max_002dspecpdl_002dsize-614] is the maximum depth of nested <code>let</code> bindings. A function call is a <code>let</code> of the parameters, even if there's no parameters, and so counts towards <code>max-specpdl-size</code> as well as <code>max-lisp-eval-depth</code>.
Line 1,161:
A tail-recursive function will run indefinitely without problems (the integer will overflow, though).
<
recurse (n+1)
recurse 0</
The non-tail recursive function of the following example crashed with a <code>StackOverflowException</code> after 39958 recursive calls:
<
printfn "%d" n
1 + recurse (n+1)
recurse 0 |> ignore</
=={{header|Factor}}==
Factor is tail-call optimized, so the following example will run without issue. In fact, Factor's iterative combinators such as <code>map</code>, <code>each</code>, and <code>times</code> are written in terms of tail recursion.
<
0 recurse</
The following non-tail recursive word caused a call stack overflow error after 65518 recursive calls in the listener.
<
: fn ( n -- n ) depth inc 1 + fn 1 + ;
[ 0 fn ] try
depth get "Recursion depth on this system is %d.\n" printf</
{{out}}
<pre>
Line 1,195:
=={{header|Fermat}}==
<
Func Sisyphus(n)=!!n;Sisyphus(n+1).
Sisyphus(0)
</syntaxhighlight>
{{out}}
<pre>
Line 1,211:
=={{header|Forth}}==
<
: test 0 ['] munge catch if ." Recursion limit at depth " . then ;
test \ Default gforth: Recursion limit at depth 3817</
Or you can just ask the system:
<
Full TCO is problematic, but a properly tail-recursive call is easy to add to any Forth. For example, in SwiftForth:
<
: test dup if 1+ recur; then drop ." I gave up finding a limit!" ;
1 test</
=={{header|Fortran}}==
<
implicit none
Line 1,248:
end subroutine recurse
end program recursion_depth</
{{out}} (snipped):
<pre>208914
Line 1,264:
=={{header|GAP}}==
The limit is around 5000 :
<
return f(n+1);
end;
Line 1,280:
# quit "brk mode" and return to GAP
quit;</
This is the default GAP recursion trap, see [http://www.gap-system.org/Manuals/doc/htm/ref/CHAP007.htm#SECT010 reference manual, section 7.10]. It enters "brk mode" after multiples of 5000 recursions levels. On can change this interval :
<
# No limit (may crash GAP if recursion is not controlled) :
SetRecursionTrapInterval(0);</
=={{header|gnuplot}}==
<
# gnuplot foo.gnuplot
Line 1,297:
print "try recurse ", try
print recurse(try)
reread</
Gnuplot 4.6 has a builtin <code>STACK_DEPTH</code> limit of 250, giving
Line 1,315:
The default can be changed by [https://golang.org/pkg/runtime/debug#SetMaxStack <code>SetMaxStack</code>] in the <code>runtime/debug</code> package. It is documented as "useful mainly for limiting the damage done by goroutines that enter an infinite recursion."
<
import (
Line 1,337:
}
r(l + 1)
}</
Run without arguments on a 64-bit system:
Line 1,455:
In Gri 2.12.23 the total depth of command calls is limited to an internal array size <code>cmd_being_done_LEN</code> which is 100. There's no protection or error check against exceeding this, so the following code segfaults shortly after 100,
<
{
show .depth.
Line 1,462:
}
.depth. = 1
Recurse</
=={{header|Groovy}}==
{{Trans|Java}}
Solution:
<
recurse = {
try {
Line 1,476:
}
recurse(0)</
{{out}}
Line 1,482:
=={{header|Haskell}}==
<
recurse :: Int -> Int
Line 1,488:
main :: IO ()
main = print $ recurse 1</
Or point-free:
<
import Data.Function (fix)
Line 1,498:
main :: IO ()
main = print $ recurse 1</
Or, more practically, testing up to a given depth:
<
testToDepth :: Int -> Int -> Int
Line 1,511:
main :: IO ()
main = print $ testToDepth 1000000 1</
{{Out}}
<pre>...
Line 1,530:
=={{header|hexiscript}}==
<
println n
rec (n + 1)
endfun
rec 1</
=={{header|HolyC}}==
The point at which a stack overflow occurs varies depending upon how many parameters passed onto the stack. Running the code from within the editor on a fresh boot of TempleOS will cause a stack overflow when <code>i</code> is larger than ~8100.
<
Print("%d\n", i);
Recurse(i + 1);
}
Recurse(0);</
=={{header|i}}==
<
print(counter)
test(counter+1)
Line 1,555:
software {
test(0)
}</
=={{header|Icon}} and {{header|Unicon}}==
<
envar := "MSTKSIZE"
write(&errout,"Program to test recursion depth - dependant on the environment variable ",envar," = ",\getenv(envar)|&null)
Line 1,569:
write( d +:= 1)
deepdive()
end</
Note: The stack size environment variable defaults to about 50000 words. This terminates after approximately 3500 recursions (Windows). The interpreter should terminate with a 301 error, but currently this does not work.
=={{header|Inform 7}}==
<
When play begins: recurse 0.
Line 1,579:
To recurse (N - number):
say "[N].";
recurse N + 1.</
Using the interpreters built into Windows build 6F95, a stack overflow occurs after 6529 recursions on the Z-machine or 2030 recursions on Glulx.
Line 1,588:
Note also that task assumes that all stack frames must be the same size, which is probably not the case.
<
This above gives a stack depth of 9998 on one machine.
Line 1,595:
=={{header|Java}}==
<syntaxhighlight lang="java">
public class RecursionTest {
Line 1,610:
}
}
</syntaxhighlight>
{{out}}
Line 1,620:
=={{header|JavaScript}}==
<
function recurse(depth)
{
Line 1,634:
var maxRecursion = recurse(1);
document.write("Recursion depth on this system is " + maxRecursion);</
{{out}} (Chrome):
Line 1,651:
'''Arity-0 Function'''
<
if (. % 1000000 == 0) then . else empty end, ((.+1)| zero_arity);
1|zero_arity</
'''Arity-1 Function'''
<
if (n % 1000 == 0) then n else empty end, with_arity(n+1);
with_arity(1)</
'''Results using jq 1.4'''
<syntaxhighlight lang="sh">
# Arity 0 - without TCO:
...
Line 1,680:
242000 # 50.0 MB (5h:14m)
# [job cancelled manually after over 5 hours]
</syntaxhighlight>
'''Results using jq with TCO'''
The arity-0 test was stopped after the recursive function had been called 100,000,000 (10^8) times. The memory required did not grow beyond 360 KB (sic).
<syntaxhighlight lang="sh">
$ time jq -n -f Find_limit_of_recursions.jq
...
Line 1,693:
user 2m0.534s
sys 0m0.329s
</syntaxhighlight>
The arity-1 test process was terminated simply because it had become too slow; at that point it had only consumed about 74.6K MB.
<syntaxhighlight lang="sh">
...
56000 # 9.9MB
Line 1,710:
406000 # 74.6 MB (8h:50m)
412000 # 74.6 MB (9h:05m)
# [job cancelled manually after over 9 hours]</
'''Discussion'''
Line 1,725:
'''Clean'''
<syntaxhighlight lang="julia">
function divedivedive(d::Int)
try
Line 1,733:
end
end
</syntaxhighlight>
'''Dirty'''
<syntaxhighlight lang="julia">
function divedivedive()
global depth
Line 1,741:
divedivedive()
end
</syntaxhighlight>
'''Main'''
<syntaxhighlight lang="julia">
depth = divedivedive(0)
println("A clean dive reaches a depth of ", depth, ".")
Line 1,752:
end
println("A dirty dive reaches a depth of ", depth, ".")
</syntaxhighlight>
{{out}}
Line 1,764:
One might have expected that the result would be the same (or only vary over a small range) for a given configuration but in fact the results are all over the place - running the program a number of times I obtained figures as high as 26400 and as low as 9099! I have no idea why.
<
fun recurse(i: Int) {
Line 1,775:
}
fun main(args: Array<String>) = recurse(0)</
{{out}}
Line 1,784:
=={{header|Liberty BASIC}}==
Checks for the case of gosub & for proper subroutine.
<syntaxhighlight lang="lb">
'subroutine recursion limit- end up on 475000
Line 1,793:
call test n+1
end sub
</
<syntaxhighlight lang="lb">
'gosub recursion limit- end up on 5767000
[test]
Line 1,801:
if n mod 1000 = 0 then locate 1,1: print n
gosub [test]
</syntaxhighlight>
=={{header|LIL}}==
lil.c allows an optional build time value to set a limit on recursion:
<
* overflows and is also useful when running through an automated fuzzer like AFL */
/*#define LIL_ENABLE_RECLIMIT 10000*/</
Otherwise, it is a race to run out of stack:
Line 1,828:
Like Scheme, Logo guarantees tail call elimination, so recursion is effectively unbounded. You can catch a user interrupt though to see how deep you could go.
<
to recurse
Line 1,838:
; hit control-C after waiting a while
print error ; 16 Stopping... recurse [make "depth :depth + 1]
(print [Depth reached:] :depth) ; some arbitrarily large number</
=={{header|LSL}}==
Line 1,846:
To test it yourself; rez a box on the ground, and add the following as a New Script.
<
Find_Limit_of_Recursion(integer x) {
llOwnerSay("x="+(string)x);
Line 1,858:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,875:
Lua (version 5.3) support proper tail call, if the recursion is proper tail call there is no limit.
Otherwise, it is limited by stack size set by the implementation.
<syntaxhighlight lang="lua">
local c = 0
function Tail(proper)
Line 1,891:
ok,check = pcall(Tail,false)
print(c, ok, check)
</syntaxhighlight>
{{out}}
<pre>
Line 1,900:
=={{header|M2000 Interpreter}}==
===Modules & Functions===
<syntaxhighlight lang="m2000 interpreter">
Module checkit {
Global z
Line 1,949:
}
Checkit
</syntaxhighlight>
In Wine give these:
<pre>
Line 1,969:
<syntaxhighlight lang="m2000 interpreter">
Module Checkit {
\\ recursion for subs controled by a value
Line 1,997:
}
Checkit
</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
The variable $RecursionLimit can be read for its current value or set to different values. eg
<syntaxhighlight lang="text">$RecursionLimit=10^6</
Would set the recursion limit to one million.
Line 2,008:
Sample Usage:
<
ans =
Line 2,019:
ans =
2500</
=={{header|Maxima}}==
<
f(0);
Maxima encountered a Lisp error:
Line 2,030:
n;
406</
=={{header|МК-61/52}}==
<syntaxhighlight lang="text">П2 ПП 05 ИП1 С/П
ИП0 ИП2 - x<0 20 ИП0 1 + П0 ПП 05
ИП1 1 + П1 В/О</
=={{header|Modula-2}}==
<
IMPORT InOut;
Line 2,051:
BEGIN
recursion (0)
END recur.</
Producing this:
<syntaxhighlight lang="modula-2">
jan@Beryllium:~/modula/rosetta$ recur >testfile
Segmentation fault
Line 2,061:
-rw-r--r-- 1 jan users 523264 2011-05-20 00:26 testfile
jan@Beryllium:~/modula/rosetta$ wc testfile
0 1 523264 testfile</
So the recursion depth is just over half a million.
=={{header|MUMPS}}==
<
IF $DATA(DEPTH)=1 SET DEPTH=1+DEPTH
IF $DATA(DEPTH)=0 SET DEPTH=1
WRITE !,DEPTH_" levels down"
DO RECURSE
QUIT</
End of the run ...<pre>
1918 levels down
Line 2,083:
=={{header|Nanoquery}}==
{{trans|Python}}
<
println counter
counter += 1
Line 2,089:
end
recurse(1)</
{{out}}
<pre>1
Line 2,101:
=={{header|Neko}}==
<syntaxhighlight lang="actionscript">/**
Recursion limit, in Neko
*/
Line 2,128:
try $print("Recurse: ", recurse(0), " sum: ", sum, "\n")
catch with $print("recurse limit exception: ", counter, " ", with, "\n")</
{{out}}
Line 2,138:
=={{header|NetRexx}}==
Like Java, NetRexx memory allocation is managed by the JVM under which it is run. The following sample presents runtime memory allocations then begins the recursion run.
<
options replace format comments java crossref symbols binary
Line 2,175:
say
return
</syntaxhighlight>
{{out}}
<pre>
Line 2,188:
=={{header|Nim}}==
<
echo i
recurse(i+1)
echo recurse(0)</
Compiled without optimizations (debug build), the program stops with the following message:
<pre>Error: call depth limit reached in a debug build (2000 function calls). You can change it with -d:nimCallDepthLimit=<int> but really try to avoid deep recursions instead.</pre>
Line 2,209:
If the recursion is not a tail one, the execution is stopped with the message
"Stack overflow":
<
val last : int ref = {contents = 0}
# let rec f i =
Line 2,219:
stack overflow during evaluation (looping recursion?).
# !last ;;
- : int = 262067</
here we see that the function call stack size is 262067.
<
let rec_limit () =
Line 2,239:
(* Since with have eaten some stack with this function, the result is slightly lower.
But now it may be used inside any function to get the available stack space *)</
=={{header|Oforth}}==
Line 2,245:
Limit found is 173510 on Windows system. Should be more on Linux system.
<
0 limit</
=={{header|ooRexx}}==
Line 2,273:
Oz supports an unbounded number of tail calls. So the following code can run forever with constant memory use (although the space used to represent <code>Number</code> will slowly increase):
<
proc {Recurse Number}
{Show Number}
Line 2,279:
end
in
{Recurse 1}</
With non-tail recursive functions, the number of recursions is only limited by the available memory.
Line 2,285:
=={{header|PARI/GP}}==
As per "Recursive functions" in the Pari/GP users's manual.
<
dive(0)</
The limit is the underlying C language stack. Deep recursion is detected before the stack is completely exhausted (by checking <code>RLIMIT_STACK</code>) so a <code>gp</code> level error is thrown instead of a segfault.
Line 2,296:
Maximum recursion depth is memory dependent.
<
recurse($x);
Line 2,302:
print ++$x,"\n";
recurse($x);
}</
Line 2,318:
On 32-bit the limit is an impressive 31 million. I have seen this hit 43 million on 64-bit, but it then forced a hard reboot.<br>
Those limits will obviously be significantly smaller for routines with more parameters, local variables, and temps.
<!--<
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time<span style="color: #0000FF;">(<span style="color: #0000FF;">)<span style="color: #0000FF;">+<span style="color: #000000;">1</span>
Line 2,336:
<span style="color: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)
<!--</
{{out|output|text= 32 bit}}
<pre>
Line 2,380:
=== saner ===
The following much more safely merely tests it can reach 20,000,000, plus however far it gets in the last whole-second
<!--<
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time<span style="color: #0000FF;">(<span style="color: #0000FF;">)<span style="color: #0000FF;">+<span style="color: #000000;">1</span>
Line 2,405:
<span style="color: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)
<!--</
{{out}}
<pre>
Line 2,418:
=={{header|PHP}}==
<
function a() {
static $i = 0;
Line 2,424:
a();
}
a();</
{{out}}
Line 2,476:
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
recurs: proc options (main) reorder;
dcl sysprint file;
Line 2,493:
call recursive();
end recurs;
</syntaxhighlight>
Result (abbreviated):
Line 2,518:
we send the results to a pipeline, we can process the earlier results before handling the
exception.
<syntaxhighlight lang="powershell">
function TestDepth ( $N )
{
Line 2,534:
}
"Last level before error: " + $Depth
</syntaxhighlight>
{{out}}
<pre>
Line 2,547:
In addition to the stack size the recursion limit for procedures is further limited by the procedure's parameters and local variables which are also stored on the same stack.
<
PrintN(str(n))
Recur(n+1)
EndProcedure
Recur(1)</
Stack overflow after 86317 recursions on x86 Vista.
===Classic===
<syntaxhighlight lang="purebasic">rec:
PrintN(str(n))
n+1
Gosub rec
Return</
Stack overflow after 258931 recursions on x86 Vista.
=={{header|Python}}==
<
print(sys.getrecursionlimit())</
To set it:
<
sys.setrecursionlimit(12345)</
Or, we can test it:
<
print(counter)
counter += 1
recurse(counter)</
Giving:
<
RecursionError: maximum recursion depth exceeded while calling a Python object
996</
Which we could change if we wanted to.
Line 2,589:
We can catch the RecursionError and keep going a bit further:
<
try:
print(counter)
Line 2,595:
except RecursionError:
print("RecursionError at depth", counter)
recurseDeeper(counter + 1)</
Giving:
<
Fatal Python error: Cannot recover from stack overflow.</
Line 2,606:
When the direct approach
<
was still churning out digits after 13,000,000 (Quackery does not optimise tail end recursion) I decided on an indirect approach, by asking the equivalent question, "What is the largest nest that Quackery can create?" as each item on the Quackery return stack occupies two items in a nest (i.e. dynamic array).
<
On the first trial the process died with a segmentation error after reaching 2^30 items, and on the second trial the computer became very unresponsive at the same point, but made it to 2^31 items before I force-quit it.
Line 2,619:
=={{header|R}}==
R's recursion is counted by the number of expressions to be evaluated, rather than the number of function calls.
<
options("expressions")
Line 2,632:
}
recurse(0)</
=={{header|Racket}}==
<
(define (recursion-limit)
(with-handlers ((exn? (lambda (x) 0)))
(add1 (recursion-limit))))</
This should theoretically return the recursion limit, as the function can't be tail-optimized and there's an exception handler to return a number when an error is encountered. For this to work one has to give the Racket VM the maximum possible memory limit and wait.
Line 2,646:
Maximum recursion depth is memory dependent. Values in excess of 1 million are easily achieved.
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang="raku"
recurse;
Line 2,653:
say $x if $x %% 1_000_000;
recurse;
}</
{{out}}
Line 2,675:
When run, this will display the address stack depth until it reaches the max depth. Once the address stack is full, Retro will crash.
<
=={{header|REXX}}==
Line 2,684:
This limit was maybe changed later to allow the user to specify the limit. My memory is really fuzzy
<br>about these details, it was over thirty years ago.
<
parse version x; say x; say /*display which REXX is being used. */
#=0 /*initialize the numbers of invokes to 0*/
Line 2,694:
#=#+1 /*bump number of times SELF is invoked. */
say # /*display the number of invocations. */
call self /*invoke ourselves recursively. */</
{{out|output|text= when using Regina 3.6 under Windows/XP Pro:}}
<pre>
Line 2,768:
===recursive subroutine===
All REXXes were executed under Windows/XP Pro.
<
parse version x; say x; say /*display which REXX is being used. */
#=0 /*initialize the numbers of invokes to 0*/
Line 2,777:
self: #=#+1 /*bump number of times SELF is invoked. */
say # /*display the number of invocations. */
call self /*invoke ourselves recursively. */</
{{out|output|text= (paraphrased and edited)}}
<pre>
Line 2,801:
=={{header|Ring}}==
<
recurse(0)
Line 2,807:
see ""+ x + nl
recurse(x+1)
</syntaxhighlight>
=={{header|Ruby}}==
<
puts x
recurse(x+1)
end
recurse(0)</
{{out}} Produces a SystemStackError:
<pre>
Line 2,829:
when tracking Stack overflow exceptions ; returns 8732 on my computer :
<
recurse(n+1)
rescue SystemStackError
Line 2,835:
end
puts recurse(0)</
=={{header|Run BASIC}}==
<
function recurTest(n)
Line 2,845:
n = recurTest(n+1)
[ext]
end function</
<pre>327000</pre>
=={{header|Rust}}==
<
println!("depth: {}", n);
recurse(n + 1)
Line 2,856:
fn main() {
recurse(0);
}</
{{out}}
Line 2,870:
=={{header|Sather}}==
<
attr r:INT;
recurse is
Line 2,881:
recurse;
end;
end;</
Segmentation fault is reached when r is 130560.
=={{header|Scala}}==
<
try{
recurseTest(i+1)
Line 2,893:
}
}
recurseTest(0)</
{{out}} depending on the current stack size:
<pre>Recursion depth on this system is 4869.</pre>
If your function is tail-recursive the compiler transforms it into a loop.
<
if(i%100000==0) println("Recursion depth is " + i + ".")
recurseTailRec(i+1)
}</
=={{header|Scheme}}==
<
(begin (display number) (newline) (recurse (+ number 1))))
(recurse 1)</
Implementations of Scheme are required to support an unbounded number of tail calls. Furthermore, implementations are encouraged, but not required, to support exact integers of practically unlimited size.
=={{header|SenseTalk}}==
<
function recurse n
put n
get the recurse of (n+1)
end recurse</
Recursion limit error is reached at 40.
=={{header|Sidef}}==
Maximum recursion depth is memory dependent.
<
say n;
recurse(n+1);
}
recurse(0);</
{{out}}
<pre>
Line 2,942:
In the Squeak dialect of Smalltalk:
<
Object subclass: #RecursionTest
instanceVariableNames: ''
Line 2,948:
poolDictionaries: ''
category: 'RosettaCode'
</syntaxhighlight>
Add the following method:
<
counter: aNumber
^self counter: aNumber + 1
</syntaxhighlight>
Call from the Workspace:
<
r := RecursionTest new.
r counter: 1.
</syntaxhighlight>
After some time the following error pops up:
Line 2,977:
Other dialects raise an exception:
<
counter := 0.
down := [ counter := counter + 1. down value ].
down on: RecursionError do:[
'depth is ' print. counter printNL
].</
=={{header|Standard ML}}==
<
1 + recLimit ()
handle _ => 0
val () = print (Int.toString (recLimit ()) ^ "\n")</
=={{header|Swift}}==
<
func recurse() {
Line 3,000:
}
recurse()</
=={{header|Tcl}}==
<
puts "This is depth [incr i]"
catch {recur $i}; # Trap error from going too deep
}
recur 0</
The tail of the execution trace looks like this:
<pre>
Line 3,017:
</pre>
Note that the maximum recursion depth is a tunable parameter, as is shown in this program:
<
interp recursionlimit {} 1000000
proc recur i {
Line 3,025:
}
}
recur 0</
For Tcl 8.5 on this platform, this prints:
<pre>
Line 3,036:
=={{header|TSE SAL}}==
<syntaxhighlight lang="tse sal">
// library: program: run: recursion: limit <description>will stop at 3616</description> <version>1.0.0.0.3</version> <version control></version control> (filenamemacro=runprrli.s) [kn, ri, su, 25-12-2011 23:12:02]
PROC PROCProgramRunRecursionLimit( INTEGER I )
Line 3,046:
PROCProgramRunRecursionLimit( 1 )
END
</syntaxhighlight>
=={{header|TXR}}==
<
(lambda (signal async-p) (throw 'out)))
Line 3,060:
(catch (recurse)
(out () (put-line `caught segfault!\nreached depth: @{*count*}`)))</
{{out}}
Line 3,071:
{{works with|Bourne Again SHell}}
<
{
# since the example runs slowly, the following
Line 3,085:
}
recurse 0</
The Bash reference manual says <cite>No limit is placed on the number of recursive calls</cite>, nonetheless a segmentation fault occurs at 13777 (Bash v3.2.19 on 32bit GNU/Linux)
=={{header|Ursa}}==
<
try
recurse (+ counter 1)
Line 3,098:
end
recurse 1</
=={{header|Vala}}==
<
print (@"$v\n");
recur( v + 1);
Line 3,108:
void main() {
recur(0);
}</
{{out}}
trimmed output
Line 3,122:
=={{header|VBA}}==
<syntaxhighlight lang="vb">
Option Explicit
Line 3,136:
Limite_Recursivite = Cpt 'return
End Function
</syntaxhighlight>
{{out}}
<pre>The limit is : 6442</pre>
Line 3,143:
Haven't figured out how to see the depth. And this depth is that of calling the O/S rather than calling within.
<
option explicit
Line 3,155:
wscript.echo "[Depth",c & "] Mung until no good."
CreateObject("WScript.Shell").Run "cscript Mung.vbs " & c, 1, true
wscript.echo "[Depth",c & "] no good."</
Okay, the internal limits version.
<
option explicit
Line 3,172:
end sub
mung 0</
{{out}} (abbrev.):
Line 3,186:
=={{header|Vlang}}==
It'll be some number, depending on machine and environment.
<
module main
Line 3,197:
println(n)
recurse(n+1)
}</
{{out}}
<pre>prompt$ v run find-limit-of-recursion.v
Line 3,210:
{{works with|nasm}}
<
section .text
Line 3,222:
add eax, 1
call recurse
ret</
I've used gdb and the command <tt>print $eax</tt> to know when the segmentation fault occurred. The result was 2094783.
Line 3,232:
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.
<
f = Fn.new { |n|
if (n%500 == 0) System.print(n) // print progress after every 500 calls
Line 3,238:
f.call(n + 1)
}
f.call(1)</
{{out}}
Line 3,255:
(For a more realistic example see this task's entry for 8080 Assembly.)
<
LD SP,&FFFF ;3 bytes
loop:
Line 3,267:
jr * ;2 bytes
;address &0024 begins here
word 0 ;placeholder for stack pointer</
This is the minimum amount of code I can come up with that can check for the limit. (Note that this code has no way to display the results of the test to the user, so on real hardware the limit of recursion is much less, but for an emulator this will suffice.) The concept here is relatively simple. Do the following in a loop:
Line 3,278:
=={{header|zkl}}==
<syntaxhighlight lang
{{out}}
<pre>
|