Find limit of recursion: Difference between revisions
added RPL
(add FreeBASIC) |
(added RPL) |
||
| (45 intermediate revisions by 23 users not shown) | |||
Line 8:
Find the limit of recursion.
<br><br>
=={{header|6502 Assembly}}==
The 6502's hardware stack isn't like other processors. First, it is fixed at the $0100-$01FF address range. The stack pointer is an 8-bit value, and assumes that the stack is always between $0100-$01FF. If the stack were to reach $01, and another <code>JSR</code> is executed, the stack would underflow to $FE, and the bottom of the stack would get clobbered. Since each JSR pushes a 2-byte return address onto the stack, the hardware limit of recursion is 128 calls.
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.
<syntaxhighlight lang="6502asm">;beginning of your program
lda #$BE
sta $0100
lda #$EF
sta $0101
ldx #$ff
txs ;stack pointer is set to $FF
;later...
lda $0100 ;if this no longer equals $BE the stack has overflowed
cmp #$BE
bne StackHasOverflowed</syntaxhighlight>
=={{header|8080 Assembly}}==
The 8080 was the first Intel processor to support a stack in RAM. (Its predecessor, the 8008,
had an on-die call stack that was limited to 7 levels.) This means it was the first one on which
recursive calls could be somewhat practical. It also set the convention that the machine stack grows
downward into memory (i.e., the topmost item on the stack is one word below the second one, etc.),
which is still true on modern Intel processors.
However, it has no support for any kind of memory protection. If the stack grows too large, it will
simply overwrite other data or code, and the program will crash. This means it is up to the programmer
to take care that this does not happen. Below are two ways of finding out the maximum recursion limit
without crashing the program. (Note that they will give slightly different answers on the same system,
as one program is slightly bigger than the other, leaving a little less room for the stack.)
===Using a stack guard===
One way of doing this is by using a stack guard (also known as a stack sentinel). The technique is to
store a word of data just beyond the last byte of memory that the program wants to use. When you do
a recursive call, you first check if it is still intact. If it isn't, the next call will overwrite
something important, so in that case, the stack is full. This way, a stack overflow can be caught
at run-time, at the cost of some overhead per call.
<syntaxhighlight lang="8080asm"> org 100h
lxi b,0 ; BC holds the amount of calls
call recur ; Call the recursive routine
;;; BC now holds the maximum amount of recursive calls one
;;; can make, and the stack is back to the beginning.
;;; Print the value in BC to the console. The stack is freed by ret
;;; so push and pop can be used.
;;; Make number into ASCII string
lxi h,num
push h
mov h,b
mov l,c
lxi b,-10
dgt: lxi d,-1
clcdgt: inx d
dad b
jc clcdgt
mov a,l
adi 10+'0'
xthl
dcx h
mov m,a
xthl
xchg
mov a,h
ora l
jnz dgt
;;; Use CP/M routine to print the string
pop d
mvi c,9
call 5
rst 0
;;; Recursive routine
recur: inx b ; Count the call
lxi d,-GUARD ; See if the guard is intact (stack not full)
lhld guard ; (subtract the original value from the
dad d ; current one)
mov a,h ; If so, the answer should be zero
ora l
cz recur ; If it is, do another recursive call
ret ; Return
;;; Placeholder for numeric output
db '00000'
num: db '$'
;;; The program doesn't need any memory after this location,
;;; so all memory beyond here is free for use by the stack.
;;; If the guard is overwritten, the stack has overflowed.
GUARD: equ $+2 ; Make sure it is not a valid return address
guard: dw GUARD</syntaxhighlight>
{{out}}
<pre>27034</pre>
(Value will differ depending on system, CP/M version, memory size, etc.)
===Calculating the value===
If all you need to know is how much room there is beforehand, it's possible to
just calculate the value. The 8080 processor decides where the stack is depending
on the <code>SP</code> (stack pointer) register, which always points to the
location of the topmost stack item (or, if the stack is considered 'empty',
it is just outside the stack).
Therefore, if you take the address of the highest byte of memory that your
program is actually using, and subtract this from <code>SP</code>, you get the
amount of free stack memory, in bytes. Because a stack item is two bytes
(addresses are 16 bits), if you then divide it by 2, you get the maximum amount
of calls you can make before the stack is full (and would overwrite your program).
<syntaxhighlight lang="8080asm"> org 100h
lxi h,-top ; Subtract highest used location from stack pointer
dad sp
xra a ; This gives bytes, but a call takes two bytes;
ora h ; so HL should be divided by two to give the actual
rar ; number.
mov h,a
mov a,l
rar
mov l,a
;;; The number of free stack words is now in HL, output it
lxi d,num
push d
lxi b,-10
dgt: lxi d,-1
clcdgt: inx d
dad b
jc clcdgt
mov a,l
adi 10+'0'
xthl
dcx h
mov m,a
xthl
xchg
mov a,h
ora l
jnz dgt
;;; Use CP/M routine to print the string
pop d
mvi c,9
call 5
rst 0
;;; Placeholder for numeric output
db '00000'
num: db '$'
;;; The program does not need any memory beyond this point.
;;; This means anything from this place up to SP is free for the
;;; stack.
top: equ $ </syntaxhighlight>
{{out}}
<pre>27039</pre>
(Value will differ depending on system, CP/M version, memory size, etc.)
=={{header|ACL2}}==
<
(if (zp x)
0
(prog2$ (cw "~x0~%" x)
(1+ (recursion-limit (1+ x))))))</
{{out}} (trimmed):
Line 31 ⟶ 187:
=={{header|Ada}}==
<
procedure Test_Recursion_Depth is
Line 43 ⟶ 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 62 ⟶ 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 97 ⟶ 253:
=={{header|AppleScript}}==
===Test 1===
A basic test for Applescript, which has a notoriously shallow recursion stack.
<
on recursionDepth()
script go
Line 117 ⟶ 274:
recursionDepth()
end run</
{{Out}}
<pre>"Recursion limit encountered at 502"</pre>
===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 215 ⟶ 373:
on succ(x)
1 + x
end succ</
{{Out}}
<pre>"The highest Church-encoded integer representable in Applescript is 571"</pre>
----
===Test 3===
The recursion limit with a fixed-length stack depends not only on the size of the stack, but on how many local variables (including parameter variables) and return addresses (including those for 'try' statements) are stored at each level. Also, of course, on where you start counting, since recursion's unlikely to begin with an empty stack in real-life situations and you may or may not regard the top call to a recursive handler as part of the recursion.
The recursive handler in the first AppleScript test above is entered with the return addresses from the 'run' and 'recursionDepth' handlers (or pointers thereto) already on the stack along with pointers to the local 'go' value and the passed 'i'. Each successive call stacks the return addresses for the 'try' statement and the handler itself along with a new 'i'. The final result of 502 is the number of times the recursive handler successfully calls itself and is probably a reasonably indicative real-world figure.
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.
<syntaxhighlight lang="applescript">global i
on recursion()
set i to i + 1
recursion()
end recursion
on run
set i to -1
try
recursion()
on error
"Recursion limit encountered at " & i
-- display dialog result -- Uncomment to see the result if running as an applet.
end try
end run</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">"Recursion limit encountered at 733"</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">recurse: function [x][
print x
recurse x+1
]
recurse 0</syntaxhighlight>
{{out}}
<pre>
...
...
...
10912
10913
10914
[2] 67851 segmentation fault arturo find\ limit\ of\ recursion.art</pre>
=={{header|AutoHotkey}}==
<
Recurse(x)
Line 226 ⟶ 431:
TrayTip, Number, %x%
Recurse(x+1)
}</
Last visible number is 827.
=={{header|AutoIt}}==
<
$depth=0
recurse($depth)
Line 237 ⟶ 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 263 ⟶ 468:
if (n > 999999) { return }
x()
}</
=={{header|Axe}}==
Line 270 ⟶ 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 291 ⟶ 496:
Utterly dependent on the stack size and RAM available to the process.
<
FUNCTION recurse(i)
PRINT i
Line 298 ⟶ 503:
END FUNCTION
extraneous = recurse(0)</
{{out}}
Line 310 ⟶ 515:
261883
Segmentation fault</pre>
==={{header|BASIC256}}===
<syntaxhighlight lang="freebasic">function Recursion(i)
print i
ext = Recursion(i + 1)
return False
end function
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}}===
<
print n
sisyphus( 1 + n )
end sub
sisyphus(0)</
{{out}}
<pre>
Line 328 ⟶ 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}}===
<syntaxhighlight lang="gwbasic">10 N#=0
20 N# = N# + 1
30 LOCATE 1,1:PRINT N#
40 GOSUB 20</syntaxhighlight>
{{out}}
<pre>
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}}===
{{works with|QBasic|1.1}}
<syntaxhighlight lang="qbasic">FUNCTION Recursion (i)
PRINT i
ext = Recursion(i + 1)
Recursion = 0
END FUNCTION
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}}===
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 342 ⟶ 619:
4/30</pre>
(The error code means "out of memory attempting to execute line <tt>30</tt>".)
==={{header|Tiny BASIC}}===
<syntaxhighlight lang="tiny basic">10 LET N = -32767
20 LET M = 0
30 LET N = N + 1
40 IF N = 32767 THEN LET M = M + 1
50 IF N = 32767 THEN PRINT M," x 2^16"
60 IF N = 32767 THEN LET N = -N
70 GOSUB 30</syntaxhighlight>
{{out}}
<pre>1 x 2^16
2 x 2^16
3 x 2^16
4 x 2^16
5 x 2^16
...
1645 x 2^16
1646 x 2^16
</pre>
I don't recommend actually running this; it will crash the computer.
==={{header|True BASIC}}===
{{works with|BASIC256}}
{{works with|QBasic}}
<syntaxhighlight lang="qbasic">FUNCTION Recursion (i)
PRINT i
LET ext = Recursion(i + 1)
LET Recursion = 0
END FUNCTION
LET ext = Recursion(0)
END</syntaxhighlight>
==={{header|XBasic}}===
{{works with|Windows XBasic}}
<syntaxhighlight lang="xbasic">PROGRAM "Find limit of recursion"
DECLARE FUNCTION Entry ()
DECLARE FUNCTION Recursion(n)
FUNCTION Entry ()
Recursion (0)
END FUNCTION
FUNCTION Recursion (i)
PRINT i
Recursion (1 + i)
END FUNCTION
END PROGRAM</syntaxhighlight>
==={{header|Yabasic}}===
<syntaxhighlight lang="freebasic">sub Recursion(i)
print i
Recursion(i + 1)
end sub
Recursion(0)</syntaxhighlight>
==={{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 358 ⟶ 693:
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 380 ⟶ 715:
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 399 ⟶ 734:
You also get the exact same results when calling mung internally, as below
<
set c=0
:mung
Line 406 ⟶ 741:
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 418 ⟶ 753:
call :mung %c%
set /a c=%1-1
echo [Level %c%] No good</
=={{header|BBC BASIC}}==
<
END
Line 427 ⟶ 762:
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 440 ⟶ 775:
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.
<syntaxhighlight lang="bqn"> {𝕊1+•Show 𝕩}0
0
1
.
.
.
4094
Error: Stack overflow
at {𝕊1+•Show 𝕩}0
</syntaxhighlight>
=={{header|Bracmat}}==
<
Observed recursion depths:
Line 452 ⟶ 800:
=={{header|C}}==
<
void recurse(unsigned int i)
Line 464 ⟶ 812:
recurse(0);
return 0;
}</
Segmentation fault occurs when i is 523756.
Line 475 ⟶ 823:
The following code may have some effect unexpected by the unwary:
<
char * base;
Line 497 ⟶ 845:
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 514 ⟶ 862:
Recur(i + 1);
}
}</
Through debugging, the highest I achieve is 14250.
Line 521 ⟶ 869:
=={{header|C++}}==
<
#include <iostream>
Line 534 ⟶ 882:
recurse(0);
}
</syntaxhighlight>
=={{header|Clojure}}==
<
=> (def *stack* 0)
=> ((fn overflow [] ((def *stack* (inc *stack*))(overflow))))
Line 543 ⟶ 891:
=> *stack*
10498
</syntaxhighlight>
=={{header|COBOL}}==
{{works with|OpenCOBOL}}
<
program-id. recurse.
data division.
Line 596 ⟶ 944:
*> 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 628 ⟶ 976:
{{works with|OpenCOBOL}}
<
PROGRAM-ID. recurse RECURSIVE.
DATA DIVISION.
Line 652 ⟶ 1,000:
EXIT PROGRAM.
END PROGRAM recurse-sub.
END PROGRAM recurse. </
Compiled with <pre>cobc -x -g recurse.cbl</pre> gives
Line 666 ⟶ 1,014:
=={{header|CoffeeScript}}==
<
recurse = ( depth = 0 ) ->
try
Line 674 ⟶ 1,022:
console.log "Recursion depth on this system is #{ do recurse }"
</syntaxhighlight>
{{out}} Example on [http://nodejs.org Node.js]:
Line 683 ⟶ 1,031:
=={{header|Common Lisp}}==
<
(defun recurse () (recurse))
(trace recurse)
(recurse)
</syntaxhighlight>
{{out}} This test was done with clisp under cygwin:
Line 701 ⟶ 1,049:
However, for an implementation of Lisp that supports proper tail recursion,
this function will not cause a stack overflow, so this method will not work.
=={{header|Crystal}}==
<syntaxhighlight lang="crystal">def recurse(counter = 0)
puts counter
recurse(counter + 1)
end
recurse()
</syntaxhighlight>
{{out}}
<pre>...
523656
Stack overflow (e.g., infinite or very deep recursion)
</pre>
=={{header|D}}==
<
void recurse(in uint i=0) {
Line 712 ⟶ 1,075:
void main() {
recurse();
}</
With the DMD compiler, using default compilation arguments, the stack overflows at 51_002.
Line 721 ⟶ 1,084:
=={{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 727 ⟶ 1,090:
65400 lhx
65600 lhx</
With the standard Ubuntu stack size limit 8MB I get
{{out}}
Line 744 ⟶ 1,107:
=={{header|Delphi}}==
{{works with|Delphi|2010 (and probably all other versions)}}
<
{$APPTYPE CONSOLE}
uses
Line 764 ⟶ 1,127:
Writeln('Press any key to Exit');
Readln;
end.</
{{out}}
Line 773 ⟶ 1,136:
Recursion limit is a parameter of script execution, which can be specified independently from the stack size to limit execution complexity.
<
procedure Recursive;
Line 786 ⟶ 1,149:
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 805 ⟶ 1,168:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
proc recurse i . .
print i
.
recurse i + 1
.
</syntaxhighlight>
<pre>
.
.
9100
InternalError: too much recursion
</pre>
Line 824 ⟶ 1,188:
=={{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 841 ⟶ 1,205:
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 872 ⟶ 1,236:
Type :help for debugging help.
Recursion depth on this system is 65518.
</pre>
=={{header|Fermat}}==
<syntaxhighlight lang="fermat">
Func Sisyphus(n)=!!n;Sisyphus(n+1).
Sisyphus(0)
</syntaxhighlight>
{{out}}
<pre>
0
1
2
...
41815
41816
Segmentation fault (core dumped)
</pre>
=={{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 912 ⟶ 1,292:
end subroutine recurse
end program recursion_depth</
{{out}} (snipped):
<pre>208914
Line 928 ⟶ 1,308:
=={{header|GAP}}==
The limit is around 5000 :
<
return f(n+1);
end;
Line 944 ⟶ 1,324:
# 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 961 ⟶ 1,341:
print "try recurse ", try
print recurse(try)
reread</
Gnuplot 4.6 has a builtin <code>STACK_DEPTH</code> limit of 250, giving
Line 979 ⟶ 1,359:
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,001 ⟶ 1,381:
}
r(l + 1)
}</
Run without arguments on a 64-bit system:
Line 1,119 ⟶ 1,499:
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,126 ⟶ 1,506:
}
.depth. = 1
Recurse</
=={{header|Groovy}}==
{{Trans|Java}}
Solution:
<
recurse = {
try {
Line 1,140 ⟶ 1,520:
}
recurse(0)</
{{out}}
Line 1,146 ⟶ 1,526:
=={{header|Haskell}}==
<
recurse :: Int -> Int
Line 1,152 ⟶ 1,532:
main :: IO ()
main = print $ recurse 1</
Or point-free:
<
import Data.Function (fix)
Line 1,162 ⟶ 1,542:
main :: IO ()
main = print $ recurse 1</
Or, more practically, testing up to a given depth:
<
testToDepth :: Int -> Int -> Int
Line 1,175 ⟶ 1,555:
main :: IO ()
main = print $ testToDepth 1000000 1</
{{Out}}
<pre>...
Line 1,194 ⟶ 1,574:
=={{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,219 ⟶ 1,599:
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,233 ⟶ 1,613:
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,243 ⟶ 1,623:
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,252 ⟶ 1,632:
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,259 ⟶ 1,639:
=={{header|Java}}==
<syntaxhighlight lang="java">
public class RecursionTest {
Line 1,274 ⟶ 1,654:
}
}
</syntaxhighlight>
{{out}}
Line 1,284 ⟶ 1,664:
=={{header|JavaScript}}==
<
function recurse(depth)
{
Line 1,298 ⟶ 1,678:
var maxRecursion = recurse(1);
document.write("Recursion depth on this system is " + maxRecursion);</
{{out}} (Chrome):
Line 1,315 ⟶ 1,695:
'''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,344 ⟶ 1,724:
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,357 ⟶ 1,737:
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,374 ⟶ 1,754:
406000 # 74.6 MB (8h:50m)
412000 # 74.6 MB (9h:05m)
# [job cancelled manually after over 9 hours]</
'''Discussion'''
Line 1,389 ⟶ 1,769:
'''Clean'''
<syntaxhighlight lang="julia">
function divedivedive(d::Int)
try
Line 1,397 ⟶ 1,777:
end
end
</syntaxhighlight>
'''Dirty'''
<syntaxhighlight lang="julia">
function divedivedive()
global depth
Line 1,405 ⟶ 1,785:
divedivedive()
end
</syntaxhighlight>
'''Main'''
<syntaxhighlight lang="julia">
depth = divedivedive(0)
println("A clean dive reaches a depth of ", depth, ".")
Line 1,416 ⟶ 1,796:
end
println("A dirty dive reaches a depth of ", depth, ".")
</syntaxhighlight>
{{out}}
Line 1,428 ⟶ 1,808:
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,439 ⟶ 1,819:
}
fun main(args: Array<String>) = recurse(0)</
{{out}}
Line 1,448 ⟶ 1,828:
=={{header|Liberty BASIC}}==
Checks for the case of gosub & for proper subroutine.
<syntaxhighlight lang="lb">
'subroutine recursion limit- end up on 475000
Line 1,457 ⟶ 1,837:
call test n+1
end sub
</
<syntaxhighlight lang="lb">
'gosub recursion limit- end up on 5767000
[test]
Line 1,465 ⟶ 1,845:
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,492 ⟶ 1,872:
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,502 ⟶ 1,882:
; 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,510 ⟶ 1,890:
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,522 ⟶ 1,902:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,539 ⟶ 1,919:
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,555 ⟶ 1,935:
ok,check = pcall(Tail,false)
print(c, ok, check)
</syntaxhighlight>
{{out}}
<pre>
Line 1,564 ⟶ 1,944:
=={{header|M2000 Interpreter}}==
===Modules & Functions===
<syntaxhighlight lang="m2000 interpreter">
Module checkit {
Global z
Line 1,613 ⟶ 1,993:
}
Checkit
</syntaxhighlight>
In Wine give these:
<pre>
Line 1,633 ⟶ 2,013:
<syntaxhighlight lang="m2000 interpreter">
Module Checkit {
\\ recursion for subs controled by a value
Line 1,661 ⟶ 2,041:
}
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 1,672 ⟶ 2,052:
Sample Usage:
<
ans =
Line 1,683 ⟶ 2,063:
ans =
2500</
=={{header|Maxima}}==
<
f(0);
Maxima encountered a Lisp error:
Line 1,694 ⟶ 2,074:
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 1,715 ⟶ 2,095:
BEGIN
recursion (0)
END recur.</
Producing this:
<syntaxhighlight lang="modula-2">
jan@Beryllium:~/modula/rosetta$ recur >testfile
Segmentation fault
Line 1,725 ⟶ 2,105:
-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 1,747 ⟶ 2,127:
=={{header|Nanoquery}}==
{{trans|Python}}
<
println counter
counter += 1
Line 1,753 ⟶ 2,133:
end
recurse(1)</
{{out}}
<pre>1
Line 1,765 ⟶ 2,145:
=={{header|Neko}}==
<syntaxhighlight lang="actionscript">/**
Recursion limit, in Neko
*/
Line 1,792 ⟶ 2,172:
try $print("Recurse: ", recurse(0), " sum: ", sum, "\n")
catch with $print("recurse limit exception: ", counter, " ", with, "\n")</
{{out}}
Line 1,802 ⟶ 2,182:
=={{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 1,839 ⟶ 2,219:
say
return
</syntaxhighlight>
{{out}}
<pre>
Line 1,852 ⟶ 2,232:
=={{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>
Compiled with option <code>-d:release</code> (release build), it terminates with a segmentation error (on Linux) after more than 673000 calls. Switching with option <code>--gc:arc</code> to “arc” memory manager, it terminates after more than 209000 calls.
Compiled with option <code>--d:danger</code> (suppressing almost all checks), it terminates with a segmentation error after more than 785000 calls. Switching to “arc” memory manager, it terminates after more than 224000 calls.
Instead of waiting for the recursions you can compile with debuginfo activated and check with gdb:
<pre>nim c -d:release --debuginfo --lineDir:on recursionlimit.nim</pre>
=={{header|OCaml}}==
Line 1,866 ⟶ 2,253:
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 1,876 ⟶ 2,263:
stack overflow during evaluation (looping recursion?).
# !last ;;
- : int = 262067</
here we see that the function call stack size is 262067.
<
let rec_limit () =
Line 1,896 ⟶ 2,283:
(* 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 1,902 ⟶ 2,289:
Limit found is 173510 on Windows system. Should be more on Linux system.
<
0 limit</
=={{header|ooRexx}}==
Line 1,930 ⟶ 2,317:
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 1,936 ⟶ 2,323:
end
in
{Recurse 1}</
With non-tail recursive functions, the number of recursions is only limited by the available memory.
Line 1,942 ⟶ 2,329:
=={{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 1,953 ⟶ 2,340:
Maximum recursion depth is memory dependent.
<
recurse($x);
Line 1,959 ⟶ 2,346:
print ++$x,"\n";
recurse($x);
}</
Line 1,973 ⟶ 2,360:
=={{header|Phix}}==
On
Those limits will obviously be significantly smaller for routines with more parameters, local variables, and temps.
<!--<syntaxhighlight lang="phix">-->
<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>
<span style="color: #004080;">integer</span> <span style="color: #000000;">depth</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time<span style="color: #0000FF;">(<span style="color: #0000FF;">)<span style="color: #0000FF;">><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?<span style="color: #000000;">depth</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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">depth</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000080;font-style:italic;">-- only 1 of these will ever get called, of course...</span>
<span style="color: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span>
<span style="color: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span>
<span style="color: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)
<!--</syntaxhighlight>-->
{{out|output|text= 32 bit}}
<pre>
C:\Program Files (x86)\Phix>p e01
Line 2,032 ⟶ 2,422:
C:\Program Files (x86)\Phix>
</pre>
=== saner ===
The following much more safely merely tests it can reach 20,000,000, plus however far it gets in the last whole-second
<!--<syntaxhighlight lang="phix">-->
<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>
<span style="color: #004080;">integer</span> <span style="color: #000000;">depth</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0<span style="color: #0000FF;">,</span> <span style="color: #000000;">depth_blown</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">btd</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"building"</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time<span style="color: #0000FF;">(<span style="color: #0000FF;">)<span style="color: #0000FF;">><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf<span style="color: #0000FF;">(<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #008000;">"depth: %d (%s)\n"<span style="color: #0000FF;">,<span style="color: #0000FF;">{<span style="color: #000000;">depth<span style="color: #0000FF;">,<span style="color: #000000;">btd<span style="color: #0000FF;">}<span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">depth<span style="color: #0000FF;">><span style="color: #000000;">20<span style="color: #000000;">_000_000</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">depth_blown</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #000000;">btd</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"tearing down"</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</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>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">depth_blown</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">depth</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">depth</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (build, aka +1 with progress)</span>
<span style="color: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (tear down, -1 with progress)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)
<!--</syntaxhighlight>-->
{{out}}
<pre>
depth: 8857573 (building)
depth: 17197111 (building)
depth: 25309477 (building)
depth: 20023696 (tearing down)
depth: 14825154 (tearing down)
depth: 9601027 (tearing down)
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}}==
<
function a() {
static $i = 0;
Line 2,041 ⟶ 2,578:
a();
}
a();</
{{out}}
Line 2,093 ⟶ 2,630:
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
recurs: proc options (main) reorder;
dcl sysprint file;
Line 2,110 ⟶ 2,647:
call recursive();
end recurs;
</syntaxhighlight>
Result (abbreviated):
Line 2,124 ⟶ 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,135 ⟶ 2,704:
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,151 ⟶ 2,720:
}
"Last level before error: " + $Depth
</syntaxhighlight>
{{out}}
<pre>
Line 2,164 ⟶ 2,733:
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,206 ⟶ 2,775:
We can catch the RecursionError and keep going a bit further:
<
try:
print(counter)
Line 2,212 ⟶ 2,781:
except RecursionError:
print("RecursionError at depth", counter)
recurseDeeper(counter + 1)</
Giving:
<
Fatal Python error: Cannot recover from stack overflow.</
=={{header|Quackery}}==
When the direct approach
<syntaxhighlight lang="quackery">0 [ 1+ dup echo cr recurse ]</syntaxhighlight>
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).
<syntaxhighlight lang="quackery">' [ 1 ] [ dup size echo cr dup join again ]</syntaxhighlight>
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.
In conclusion, the answer to the question "What depth of recursion does Quackery support?", at least in the case of Quackery running under Python 3.8.1 on a mid 2011 iMac with a 2.5 GHz Intel Core i5 and 12 GB of RAM and MacOS 10.13.6, is "sufficient".
I would anticipate at least equivalent results running under PyPy3, as it has much better garbage collection. (Also, it runs Quackery 20 to 30 times faster than the default version of Python 3, so would crash significantly sooner.)
=={{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,234 ⟶ 2,818:
}
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,248 ⟶ 2,832:
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,255 ⟶ 2,839:
say $x if $x %% 1_000_000;
recurse;
}</
{{out}}
Line 2,277 ⟶ 2,861:
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,286 ⟶ 2,870:
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,296 ⟶ 2,880:
#=#+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,370 ⟶ 2,954:
===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,379 ⟶ 2,963:
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,403 ⟶ 2,987:
=={{header|Ring}}==
<
recurse(0)
Line 2,409 ⟶ 2,993:
see ""+ x + nl
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}}==
<
puts x
recurse(x+1)
end
recurse(0)</
{{out}} Produces a SystemStackError:
<pre>
Line 2,431 ⟶ 3,021:
when tracking Stack overflow exceptions ; returns 8732 on my computer :
<
recurse(n+1)
rescue SystemStackError
Line 2,437 ⟶ 3,027:
end
puts recurse(0)</
=={{header|Run BASIC}}==
<
function recurTest(n)
Line 2,447 ⟶ 3,037:
n = recurTest(n+1)
[ext]
end function</
<pre>327000</pre>
=={{header|Rust}}==
<
println!("depth: {}", n);
recurse(n + 1)
Line 2,458 ⟶ 3,048:
fn main() {
recurse(0);
}</
{{out}}
Line 2,472 ⟶ 3,062:
=={{header|Sather}}==
<
attr r:INT;
recurse is
Line 2,483 ⟶ 3,073:
recurse;
end;
end;</
Segmentation fault is reached when r is 130560.
=={{header|Scala}}==
<
try{
recurseTest(i+1)
Line 2,495 ⟶ 3,085:
}
}
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,544 ⟶ 3,134:
In the Squeak dialect of Smalltalk:
<
Object subclass: #RecursionTest
instanceVariableNames: ''
Line 2,550 ⟶ 3,140:
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,579 ⟶ 3,169:
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}}==
<syntaxhighlight lang="sml">fun recLimit () =
1 + recLimit ()
handle _ => 0
val () = print (Int.toString (recLimit ()) ^ "\n")</syntaxhighlight>
=={{header|Swift}}==
<
func recurse() {
Line 2,595 ⟶ 3,192:
}
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 2,612 ⟶ 3,209:
</pre>
Note that the maximum recursion depth is a tunable parameter, as is shown in this program:
<
interp recursionlimit {} 1000000
proc recur i {
Line 2,620 ⟶ 3,217:
}
}
recur 0</
For Tcl 8.5 on this platform, this prints:
<pre>
Line 2,631 ⟶ 3,228:
=={{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 2,641 ⟶ 3,238:
PROCProgramRunRecursionLimit( 1 )
END
</syntaxhighlight>
=={{header|TXR}}==
<
(lambda (signal async-p) (throw 'out)))
Line 2,655 ⟶ 3,252:
(catch (recurse)
(out () (put-line `caught segfault!\nreached depth: @{*count*}`)))</
{{out}}
Line 2,666 ⟶ 3,263:
{{works with|Bourne Again SHell}}
<
{
# since the example runs slowly, the following
Line 2,680 ⟶ 3,277:
}
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 2,693 ⟶ 3,290:
end
recurse 1</
=={{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}}==
<syntaxhighlight lang="vala">void recur(uint64 v ) {
print (@"$v\n");
recur( v + 1);
}
void main() {
recur(0);
}</syntaxhighlight>
{{out}}
trimmed output
<pre>0
1
2
...
25905
25906
25907
</pre>
=={{header|VBA}}==
<syntaxhighlight lang="vb">
Option Explicit
Line 2,711 ⟶ 3,380:
Limite_Recursivite = Cpt 'return
End Function
</syntaxhighlight>
{{out}}
<pre>The limit is : 6442</pre>
Line 2,718 ⟶ 3,387:
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 2,730 ⟶ 3,399:
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 2,747 ⟶ 3,416:
end sub
mung 0</
{{out}} (abbrev.):
Line 2,758 ⟶ 3,427:
[Level 1720] no good
[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
// starts here, then call down until stacks become faulty
pub fn main() {
recurse(0)
}
fn recurse(n int) {
println(n)
recurse(n+1)
}</syntaxhighlight>
{{out}}
<pre>prompt$ v run find-limit-of-recursion.v
...
174537
174538
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 2,763 ⟶ 3,474:
{{works with|nasm}}
<
section .text
Line 2,775 ⟶ 3,486:
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.
=={{header|XPL0}}==
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>
=={{header|Z80 Assembly}}==
Unlike the 6502, the Z80 has a 16-bit stack pointer that is fully relocatable. Therefore, the limit of recursion technically depends on how much RAM you have. The definition of "limit for recursion" for this example is maximum number of instructions that have a <code>push</code> effect (including <code>push</code>, <code>call</code>, <code>rst</code>, etc.),before RAM that was not intended to be part of the stack area (i.e. the heap) becomes clobbered. For this task we'll assume that interrupts are disabled, and no hardware exists that would generate an NMI. (Both of those operations put return addresses on the stack and can do so at any time during our code execution so for simplicity we'll ignore them.
To give the maximum limit, we'll say that there is only one variable (we need one to store the stack pointer), and the entire address space of the CPU exists and is in RAM (i.e. 64k of RAM, including the beginning vector table, program code, and stack space, no address mirroring. Also we'll assume there is no "video memory" or anything not intended for a specific purpose.) A byte count of each line of code is also provided.
(For a more realistic example see this task's entry for 8080 Assembly.)
<syntaxhighlight lang="z80">org &0000
LD SP,&FFFF ;3 bytes
loop:
or a ;1 byte, clears the carry flag
ld (&0024),sp ;4 bytes
ld hl,(&0024) ;3 bytes
push af ;1 byte
ld bc,(&0024) ;4 bytes
sbc hl,bc ;4 bytes
jr z,loop ;2 bytes
jr * ;2 bytes
;address &0024 begins here
word 0 ;placeholder for stack pointer</syntaxhighlight>
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:
* Store the stack pointer into memory.
* Load it into HL.
* Push a value. This will cause the real stack pointer to decrement and the pushed value will be written to memory.
* After the push, load from the same memory location into BC. If we haven't reached the limit of recursion, HL = BC.
* 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}}==
<syntaxhighlight lang
{{out}}
<pre>
| |||