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>

Segmentation fault (core dumped)

</pre>

 

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

20 N# = N# + 1

30 LOCATE 1,1:PRINT N#

{{out}}

<pre>

33

Out of memory in 20.</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}}==

 

.

<pre>

.

.

</pre>

 

 

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

<span style="color: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)

{{out|output|text=&nbsp; 32 bit}}

<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

<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: #000000;">recurse<span style="color: #0000FF;">(<span style="color: #0000FF;">)

{{out}}

<pre>

depth: 3725849 (tearing down)

</pre>

 

=={{header|PHP}}==

function a() {

static $i = 0;

a();

}

 

{{out}}

 

=={{header|PL/I}}==

recurs: proc options (main) reorder;

dcl sysprint file;

call recursive();

end recurs;

 

Result (abbreviated):

 

Obviously, if the procedure '''recursive''' would have contained local variables, the depth of recursion would be reached much earlier...

 

=={{header|PowerShell}}==

we send the results to a pipeline, we can process the earlier results before handling the

exception.

function TestDepth ( $N )

{

}

"Last level before error: " + $Depth

{{out}}

<pre>

 

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

 

Stack overflow after 86317 recursions on x86 Vista.

 

===Classic===

PrintN(str(n))

n+1

Gosub rec

Stack overflow after 258931 recursions on x86 Vista.

 

=={{header|Python}}==

 

To set it:

 

 

Or, we can test it:

 

print(counter)

counter += 1

 

Giving:

 

RecursionError: maximum recursion depth exceeded while calling a Python object

 

Which we could change if we wanted to.

We can catch the RecursionError and keep going a bit further:

 

try:

print(counter)

except RecursionError:

print("RecursionError at depth", counter)

 

Giving:

 

 

 

 

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.

 

=={{header|R}}==

R's recursion is counted by the number of expressions to be evaluated, rather than the number of function calls.

options("expressions")

 

 

}

 

=={{header|Racket}}==

(define (recursion-limit)

(with-handlers ((exn? (lambda (x) 0)))

 

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.

Maximum recursion depth is memory dependent. Values in excess of 1 million are easily achieved.

{{works with|Rakudo|2015.12}}

recurse;

 

say $x if $x %% 1_000_000;

recurse;

 

{{out}}

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

This limit was maybe changed later to allow the user to specify the limit. &nbsp; 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*/

#=#+1 /*bump number of times SELF is invoked. */

say # /*display the number of invocations. */

{{out|output|text=&nbsp; when using Regina 3.6 under Windows/XP Pro:}}

<pre>

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

self: #=#+1 /*bump number of times SELF is invoked. */

say # /*display the number of invocations. */

{{out|output|text=&nbsp; (paraphrased and edited)}}

<pre>

 

=={{header|Ring}}==

recurse(0)

 

see ""+ x + nl

recurse(x+1)

 

=={{header|Ruby}}==

puts x

recurse(x+1)

end

 

{{out}} Produces a SystemStackError:

<pre>

when tracking Stack overflow exceptions ; returns 8732 on my computer :

 

recurse(n+1)

rescue SystemStackError

end

 

 

=={{header|Run BASIC}}==

function recurTest(n)

n = recurTest(n+1)

[ext]

<pre>327000</pre>

 

=={{header|Rust}}==

println!("depth: {}", n);

recurse(n + 1)

fn main() {

recurse(0);

 

{{out}}

 

=={{header|Sather}}==

attr r:INT;

recurse is

recurse;

end;

 

Segmentation fault is reached when r is 130560.

 

=={{header|Scala}}==

try{

recurseTest(i+1)

}

}

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

 

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)

Recursion limit error is reached at 40.

 

=={{header|Sidef}}==

Maximum recursion depth is memory dependent.

say n;

recurse(n+1);

}

 

{{out}}

<pre>

In the Squeak dialect of Smalltalk:

 

Object subclass: #RecursionTest

instanceVariableNames: ''

poolDictionaries: ''

category: 'RosettaCode'

 

Add the following method:

 

counter: aNumber

^self counter: aNumber + 1

 

Call from the Workspace:

 

r := RecursionTest new.

r counter: 1.

 

After some time the following error pops up:

 

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

 

 

=={{header|Swift}}==

 

func recurse() {

}

 

 

=={{header|Tcl}}==

puts "This is depth [incr i]"

catch {recur $i}; # Trap error from going too deep

}

The tail of the execution trace looks like this:

<pre>

</pre>

Note that the maximum recursion depth is a tunable parameter, as is shown in this program:

interp recursionlimit {} 1000000

proc recur i {

}

}

For Tcl 8.5 on this platform, this prints:

<pre>

 

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

PROCProgramRunRecursionLimit( 1 )

END

 

=={{header|TXR}}==

 

(lambda (signal async-p) (throw 'out)))

 

 

(catch (recurse)

 

{{out}}

{{works with|Bourne Again SHell}}

 

{

# since the example runs slowly, the following

}

 

 

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)

end

 

 

=={{header|Vala}}==

print (@"$v\n");

recur( v + 1);

void main() {

recur(0);

{{out}}

trimmed output

=={{header|VBA}}==

 

Option Explicit

 

Limite_Recursivite = Cpt 'return

End Function

{{out}}

<pre>The limit is : 6442</pre>

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

 

wscript.echo "[Depth",c & "] Mung until no good."

CreateObject("WScript.Shell").Run "cscript Mung.vbs " & c, 1, true

 

Okay, the internal limits version.

 

option explicit

 

end sub

 

 

{{out}} (abbrev.):

[Level 1719] no good</pre>

 

It'll be some number, depending on machine and environment.

module main

 

println(n)

recurse(n+1)

{{out}}

<pre>prompt$ v run find-limit-of-recursion.v

prompt$ echo $?

11</pre>

 

=={{header|x86 Assembly}}==

{{works with|nasm}}

 

 

section .text

add eax, 1

call recurse

 

I've used gdb and the command <tt>print $eax</tt> to know when the segmentation fault occurred. The result was 2094783.

 

 

 

 

{{out}}

<pre>

</pre>

 

(For a more realistic example see this task's entry for 8080 Assembly.)

 

LD SP,&FFFF ;3 bytes

loop:

jr * ;2 bytes

;address &0024 begins here

 

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:

* 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|zkl}}==

{{out}}

<pre>