Find limit of recursion: Difference between revisions

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

lda $0100 ;if this no longer equals $BE the stack has overflowed

cmp #$BE

=={{header|8080 Assembly}}==

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

;;; If the guard is overwritten, the stack has overflowed.

GUARD: equ $+2 ; Make sure it is not a valid return address

{{out}}

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

;;; This means anything from this place up to SP is free for the

;;; stack.

{{out}}

=={{header|ACL2}}==

(if (zp x)

0

(prog2$ (cw "~x0~%" x)

{{out}} (trimmed):

=={{header|Ada}}==

procedure Test_Recursion_Depth is

begin

Put_Line ("Recursion depth on this system is" & Integer'Image (Recursion (1)));

Note that unlike some solutions in other languages this one does not crash (though usefulness of this task is doubtful).

=={{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.

===Test 1===

A basic test for Applescript, which has a notoriously shallow recursion stack.

on recursionDepth()

script go

recursionDepth()

{{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)

on succ(x)

1 + x

{{Out}}

<pre>"The highest Church-encoded integer representable in Applescript is 571"</pre>

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()

-- display dialog result -- Uncomment to see the result if running as an applet.

end try

{{output}}

=={{header|Arturo}}==

print x

recurse x+1

]

{{out}}

=={{header|AutoHotkey}}==

Recurse(x)

TrayTip, Number, %x%

Recurse(x+1)

Last visible number is 827.

=={{header|AutoIt}}==

$depth=0

recurse($depth)

ConsoleWrite($depth&@CRLF)

Return recurse($depth+1)

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

if (n > 999999) { return }

x()

=={{header|Axe}}==

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

=={{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

{{out}}

<pre>RECURSION DEPTH

Utterly dependent on the stack size and RAM available to the process.

FUNCTION recurse(i)

PRINT i

END FUNCTION

{{out}}

==={{header|BASIC256}}===

print i

ext = Recursion(i + 1)

end function

==={{header|FreeBASIC}}===

print n

sisyphus( 1 + n )

end sub

{{out}}

<pre>

==={{header|GW-BASIC}}===

20 N# = N# + 1

30 LOCATE 1,1:PRINT N#

{{out}}

<pre>

==={{header|QBasic}}===

{{works with|QBasic|1.1}}

PRINT i

ext = Recursion(i + 1)

END FUNCTION

==={{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

{{out}}

Run with 1k of RAM:

==={{header|Tiny BASIC}}===

20 LET M = 0

30 LET N = N + 1

50 IF N = 32767 THEN PRINT M," x 2^16"

60 IF N = 32767 THEN LET N = -N

{{out}}

<pre>1 x 2^16

{{works with|BASIC256}}

{{works with|QBasic}}

PRINT i

LET ext = Recursion(i + 1)

LET ext = Recursion(0)

==={{header|XBasic}}===

{{works with|Windows XBasic}}

DECLARE FUNCTION Entry ()

END FUNCTION

==={{header|Yabasic}}===

print i

Recursion(i + 1)

end sub

==={{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

{{out}}(from a 48k Spectrum):

<pre> Recursion depth: 13792

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

Result (abbreviated):

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

Result (abbreviated):

You also get the exact same results when calling mung internally, as below

set c=0

:mung

call :mung

set /a c=c-1

Setting a limit on the recursion depth can be done like this:

set c=0

:mung

call :mung %c%

set /a c=%1-1

=={{header|BBC BASIC}}==

END

IF depth% MOD 100 = 0 PRINT TAB(0,0) depth%;

PROCrecurse(depth% + 1)

{{out}} from BBC BASIC for Windows with default value of HIMEM:

<pre>

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

Error: Stack overflow

at {𝕊1+•Show 𝕩}0

=={{header|Bracmat}}==

Observed recursion depths:

=={{header|C}}==

void recurse(unsigned int i)

recurse(0);

return 0;

Segmentation fault occurs when i is 523756.

The following code may have some effect unexpected by the unwary:

char * base;

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

{

Recur(i + 1);

}

Through debugging, the highest I achieve is 14250.

=={{header|C++}}==

#include <iostream>

recurse(0);

}

=={{header|Clojure}}==

=> (def *stack* 0)

=> ((fn overflow [] ((def *stack* (inc *stack*))(overflow))))

=> *stack*

10498

=={{header|COBOL}}==

{{works with|OpenCOBOL}}

program-id. recurse.

data division.

*> room for a better-than-abrupt death here.

Compiled with <pre>cobc -free -x -g recurse.cbl</pre> gives, after a while,

<pre>...

{{works with|OpenCOBOL}}

PROGRAM-ID. recurse RECURSIVE.

DATA DIVISION.

EXIT PROGRAM.

END PROGRAM recurse-sub.

Compiled with <pre>cobc -x -g recurse.cbl</pre> gives

=={{header|CoffeeScript}}==

recurse = ( depth = 0 ) ->

try

console.log "Recursion depth on this system is #{ do recurse }"

{{out}} Example on [http://nodejs.org Node.js]:

=={{header|Common Lisp}}==

(defun recurse () (recurse))

(trace recurse)

(recurse)

{{out}} This test was done with clisp under cygwin:

=={{header|Crystal}}==

puts counter

recurse(counter + 1)

recurse()

{{out}}

=={{header|D}}==

void recurse(in uint i=0) {

void main() {

recurse();

With the DMD compiler, using default compilation arguments, the stack overflows at 51_002.

=={{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

65400 lhx

With the standard Ubuntu stack size limit 8MB I get

{{out}}

=={{header|Delphi}}==

{{works with|Delphi|2010 (and probably all other versions)}}

{$APPTYPE CONSOLE}

uses

Writeln('Press any key to Exit');

Readln;

{{out}}

Recursion limit is a parameter of script execution, which can be specified independently from the stack size to limit execution complexity.

procedure Recursive;

Recursive;

=={{header|Déjà Vu}}==

{{untested|Déjà Vu}}

!. n

rec-fun ++ n

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.

=={{header|EasyLang}}==

print i

call recurse i + 1

.

<pre>

0

=={{header|Emacs Lisp}}==

(my-recurse (1+ n)))

(my-recurse 1)

=>

enters debugger at (my-recurse 595),

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>.

A tail-recursive function will run indefinitely without problems (the integer will overflow, though).

recurse (n+1)

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)

=={{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.

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

{{out}}

<pre>

=={{header|Fermat}}==

Func Sisyphus(n)=!!n;Sisyphus(n+1).

Sisyphus(0)

{{out}}

<pre>

=={{header|Forth}}==

: test 0 ['] munge catch if ." Recursion limit at depth " . then ;

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!" ;

=={{header|Fortran}}==

implicit none

end subroutine recurse

{{out}} (snipped):

<pre>208914

=={{header|GAP}}==

The limit is around 5000 :

return f(n+1);

end;

# quit "brk mode" and return to GAP

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) :

=={{header|gnuplot}}==

# gnuplot foo.gnuplot

print "try recurse ", try

print recurse(try)

Gnuplot 4.6 has a builtin <code>STACK_DEPTH</code> limit of 250, giving

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 (

}

r(l + 1)

Run without arguments on a 64-bit system:

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.

}

.depth. = 1

=={{header|Groovy}}==

{{Trans|Java}}

Solution:

recurse = {

try {

}

{{out}}

=={{header|Haskell}}==

recurse :: Int -> Int

main :: IO ()

Or point-free:

import Data.Function (fix)

main :: IO ()

Or, more practically, testing up to a given depth:

testToDepth :: Int -> Int -> Int

main :: IO ()

{{Out}}

<pre>...

=={{header|hexiscript}}==

println n

rec (n + 1)

endfun

=={{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);

}

=={{header|i}}==

print(counter)

test(counter+1)

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)

write( d +:= 1)

deepdive()

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.

To recurse (N - number):

say "[N].";

Using the interpreters built into Windows build 6F95, a stack overflow occurs after 6529 recursions on the Z-machine or 2030 recursions on Glulx.

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.

=={{header|Java}}==

public class RecursionTest {

}

}

{{out}}

=={{header|JavaScript}}==

function recurse(depth)

{

var maxRecursion = recurse(1);

{{out}} (Chrome):

'''Arity-0 Function'''

if (. % 1000000 == 0) then . else empty end, ((.+1)| zero_arity);

'''Arity-1 Function'''

if (n % 1000 == 0) then n else empty end, with_arity(n+1);

'''Results using jq 1.4'''

# Arity 0 - without TCO:

...

242000 # 50.0 MB (5h:14m)

# [job cancelled manually after over 5 hours]

'''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).

$ time jq -n -f Find_limit_of_recursions.jq

...

user 2m0.534s

sys 0m0.329s

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.

...

56000 # 9.9MB

406000 # 74.6 MB (8h:50m)

412000 # 74.6 MB (9h:05m)

'''Discussion'''

'''Clean'''

function divedivedive(d::Int)

try

end

end

'''Dirty'''

function divedivedive()

global depth

divedivedive()

end

'''Main'''

depth = divedivedive(0)

println("A clean dive reaches a depth of ", depth, ".")

end

println("A dirty dive reaches a depth of ", depth, ".")

{{out}}

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) {

}

{{out}}

=={{header|Liberty BASIC}}==

Checks for the case of gosub & for proper subroutine.

'subroutine recursion limit- end up on 475000

call test n+1

end sub

'gosub recursion limit- end up on 5767000

[test]

if n mod 1000 = 0 then locate 1,1: print n

gosub [test]

=={{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 */

Otherwise, it is a race to run out of stack:

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

; hit control-C after waiting a while

print error ; 16 Stopping... recurse [make "depth :depth + 1]

=={{header|LSL}}==

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);

}

}

{{out}}

<pre>

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.

local c = 0

function Tail(proper)

ok,check = pcall(Tail,false)

print(c, ok, check)

{{out}}

<pre>

=={{header|M2000 Interpreter}}==

===Modules & Functions===

Module checkit {

Global z

}

Checkit

In Wine give these:

<pre>

Module Checkit {

\\ recursion for subs controled by a value

}

Checkit

=={{header|Mathematica}} / {{header|Wolfram Language}}==

The variable $RecursionLimit can be read for its current value or set to different values. eg

Would set the recursion limit to one million.

Sample Usage:

ans =

ans =

=={{header|Maxima}}==

f(0);

Maxima encountered a Lisp error:

n;

=={{header|МК-61/52}}==

ИП0 ИП2 - x<0 20 ИП0 1 + П0 ПП 05

=={{header|Modula-2}}==

IMPORT InOut;

BEGIN

recursion (0)

Producing this:

jan@Beryllium:~/modula/rosetta$ recur >testfile

Segmentation fault

-rw-r--r-- 1 jan users 523264 2011-05-20 00:26 testfile

jan@Beryllium:~/modula/rosetta$ wc 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

End of the run ...<pre>

1918 levels down

=={{header|Nanoquery}}==

{{trans|Python}}

println counter

counter += 1

end

{{out}}

<pre>1

=={{header|Neko}}==

Recursion limit, in Neko

*/

try $print("Recurse: ", recurse(0), " sum: ", sum, "\n")

{{out}}

=={{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

say

return

{{out}}

<pre>

=={{header|Nim}}==

echo i

recurse(i+1)

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>

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 =

stack overflow during evaluation (looping recursion?).

# !last ;;

here we see that the function call stack size is 262067.

let rec_limit () =

(* Since with have eaten some stack with this function, the result is slightly lower.

=={{header|Oforth}}==

Limit found is 173510 on Windows system. Should be more on Linux system.

=={{header|ooRexx}}==

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}

end

in

With non-tail recursive functions, the number of recursions is only limited by the available memory.

=={{header|PARI/GP}}==

As per "Recursive functions" in the Pari/GP users's manual.

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.

Maximum recursion depth is memory dependent.

recurse($x);

print ++$x,"\n";

recurse($x);

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>