Find limit of recursion

Find limit of recursion
You are encouraged to solve this task according to the task description, using any language you may know.

Find limit of recursion is part of Short Circuit's Console Program Basics selection.

Find the limit of recursion.

ACL2

<lang Lisp>(defun recursion-limit (x)

  (if (zp x)
      0
      (prog2$ (cw "~x0~%" x)
              (1+ (recursion-limit (1+ x))))))</lang>

Output (trimmed):

87195
87196
87197
87198
87199
87200
87201

***********************************************
************ ABORTING from raw Lisp ***********
Error:  Stack overflow on value stack.
***********************************************

Ada

<lang Ada>with Ada.Text_IO; use Ada.Text_IO;

procedure Test_Recursion_Depth is

  function Recursion (Depth : Positive) return Positive is
  begin
     return Recursion (Depth + 1);
  exception
     when Storage_Error =>
        return Depth;
  end Recursion;

begin

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

end Test_Recursion_Depth;</lang> Note that unlike some solutions in other languages this one does not crash (though usefulness of this task is doubtful).

In Ada Storage_Error exception is propagated when there is no free memory to accomplish the requested action. In particular it is propagated upon stack overflow within the task where this occurs. Storage_Error can be handled without termination of the task. In the solution the function Recursion calls itself or else catches Storage_Error indicating stack overflow.

Note that this technique requires some care, because there must be enough stack space for the handler to work. In this case it works because the handler just return the current call depth. In real-life Storage_Error is usually fatal.

Sample output:

Recursion depth on this system is 524091

AutoHotkey

<lang AutoHotkey>Recurse(0)

Recurse(x) {

 TrayTip, Number, %x%
 Recurse(x+1)

}</lang>

Last visible number is 827.

AutoIt

<lang AutoIt>;AutoIt Version: 3.2.10.0 $depth=0 recurse($depth) Func recurse($depth)

  ConsoleWrite($depth&@CRLF)
  Return recurse($depth+1)

EndFunc</lang> Last value of $depth is 5099 before error. Error: Recursion level has been exceeded - AutoIt will quit to prevent stack overflow.

AWK

<lang AWK># syntax: GAWK -f FIND_LIMIT_OF_RECURSION.AWK

2. contributed by Dan Nielsen
3. modified by contributors to Rosetta Code
5. version depth messages
6. ------------------ ----- --------
7. GAWK 3.1.4 2892 none
8. XML GAWK 3.1.4 3026 none
9. GAWK 4.0 >999999
10. MAWK 1.3.3 4976 A stack overflow was encountered at
11. address 0x7c91224e.
12. TAWK-DOS AWK 5.0c 357 stack overflow
13. TAWK-WIN AWKW 5.0c 2477 awk stack overflow
14. NAWK 20100523 4351 Segmentation fault (core dumped)

BEGIN {

   x()
   print("done")

} function x() {

   print(++n)
   if (n > 999999) { return }
   x()

}</lang>

Batch File

MUNG.CMD is a commandline tool written in DOS Batch language. It finds the limit of recursion possible using CMD /C.

<lang dos>@echo off 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</lang>

Result (abbreviated):

...
[Depth 259] Mung until no good
[Depth 260] Mung until no good
[Depth 261] Mung until no good
[Depth 261] No good
[Depth 260] No good
[Depth 259] No good
...

If one uses call rather than CMD/C, the call depth is much deeper but ends abruptly and can't be trapped.

<lang dos>@echo off 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</lang>

Result (abbreviated):

1240: Mung until no good
1241: Mung until no good
******  B A T C H   R E C U R S I O N  exceeds STACK limits ******
Recursion Count=1240, Stack Usage=90 percent
******       B A T C H   PROCESSING IS   A B O R T E D      ******

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

<lang dos>@echo off set c=0

mung

set /a c=c+1 echo [Level %c%] Mung until no good call :mung set /a c=c-1 echo [Level %c%] No good</lang>

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

<lang dos>@echo off set c=0

mung

set /a c=%1+1 if %c%==10 goto :eof echo [Level %c%] Mung until no good call :mung %c% set /a c=%1-1 echo [Level %c%] No good</lang>

BASIC

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: <lang zxbasic> 10 LET d=0: REM depth 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 </lang>

Output (from a 48k Spectrum): {{{

Recursion depth: 13792
4 Out of memory, 110:1

}}}

Bracmat

<lang bracmat>rec=.out$!arg&rec$(!arg+1)</lang>

Observed recursion depths:

 Windows XP command prompt: 6588
 Linux: 18276

Bracmat crashes when it tries to exceed the maximum recursion depth.

C

<lang c>#include <stdio.h>

void recurse(unsigned int i) {

 printf("%d\n", i);
 recurse(i+1); // 523756

}

int main() {

 recurse(0);
 return 0;

}</lang>

Segmentation fault occurs when i is 523756. (This was checked debugging with gdb rather than waiting the output: the printf line for the test was commented). It must be noted that the recursion limit depends on how many parameters are passed onto the stack. E.g. adding a fake double argument to recurse, the limit is reached at i == 261803. The limit depends on the stack size and usage in the function. Even if there are no arguments, the return address for a call to a subroutine is stored on the stack (at least on x86 and many more processors), so this is consumed even if we put arguments into registers.

The following code may have some effect unexpected by the unwary: <lang C>#include <stdio.h>

char * base; void get_diff() { char x; if (base - &x < 200) printf("%p %d\n", &x, base - &x); }

void recur() { get_diff(); recur(); }

int main() { char v = 32; printf("pos of v: %p\n", base = &v); recur(); return 0; }</lang> With GCC 4.5, if compiled without -O2, it segfaults quickly; if gcc -O2, crash never happens, because the optimizer noticed the tail recursion in recur() and turned it into a loop!

COBOL

Works with: OpenCOBOL 1.1

<lang cobol>identification division. program-id. recurse. data division. working-storage section. 01 depth-counter pic 9(3). 01 install-address usage is procedure-pointer. 01 install-flag pic x comp-x value 0. 01 status-code pic x(2) comp-5. 01 ind pic s9(9) comp-5.

linkage section. 01 err-msg pic x(325).

procedure division. 100-main.

set install-address to entry "300-err".

call "CBL_ERROR_PROC" using install-flag install-address returning status-code.

if status-code not = 0 display "ERROR INSTALLING ERROR PROC" stop run

       end-if

	move 0 to depth-counter.

display 'Mung until no good.'. perform 200-mung. display 'No good.'. stop run.

200-mung. add 1 to depth-counter. display depth-counter. perform 200-mung. 300-err. entry "300-err" using err-msg. perform varying ind from 1 by 1 until (err-msg(ind:1) = x"00") or (ind = length of err-msg) continue end-perform

display err-msg(1:ind).

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

exit program.</lang>

Compiled with

cobc -free -x -g recurse.cbl

gives, after a while,

...
249
250
251
252
253
Trapped: recurse.cob:38: Stack overflow, possible PERFORM depth exceeded
recurse.cob:50: libcob: Stack overflow, possible PERFORM depth exceeded

Without stack-checking turned on (achieved with -g in this case), it gives

...
249
250
251
252
253
254
255
256
257
Attempt to reference unallocated memory (Signal SIGSEGV)
Abnormal termination - File contents may be incorrect

which suggests that -g influences the functionality of CBL_ERROR_PROC

Thanks to Brian Tiffin for his demo code on opencobol.org's forum

A more 'canonical' way of doing it

from Richard Plinston on comp.lang.cobol

Works with: OpenCOBOL 1.1

<lang cobol> IDENTIFICATION DIVISION.

      PROGRAM-ID.          recurse RECURSIVE.
      DATA DIVISION.
      WORKING-STORAGE SECTION.
      01  Starter          PIC S9(8) VALUE 1.
      PROCEDURE DIVISION.
      Program-Recurse.
          CALL "recurse-sub" USING Starter
          STOP RUN.

      IDENTIFICATION DIVISION.
      PROGRAM-ID.          recurse-sub.
      DATA DIVISION.
      WORKING-STORAGE SECTION.
      LINKAGE SECTION.
      01  Countr                      PIC S9(8).
      PROCEDURE DIVISION USING Countr.
      Program-Recursive.
          DISPLAY Countr
          ADD 1   TO Countr
          CALL "recurse-sub" USING Countr

          EXIT PROGRAM.
      END PROGRAM recurse-sub.
      END PROGRAM recurse. </lang>

Compiled with

cobc -x -g recurse.cbl

gives

...
+00000959
+00000960
+00000961
+00000962
+00000963
+00000964
recurse.cbl:19: Attempt to reference unallocated memory (Signal SIGSEGV)
Abnormal termination - File contents may be incorrect

Common Lisp

<lang lisp> (defun recurse () (recurse)) (trace recurse) (recurse) </lang>

end of output, This test was done with clisp under cygwin:

3056. Trace: (RECURSE)
3057. Trace: (RECURSE)
3058. Trace: (RECURSE)
3059. Trace: (RECURSE)

*** - Lisp stack overflow. RESET

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.

C#

<lang csharp>using System; class RecursionLimit {

 static void Main(string[] args)
 {
   Recur(0);
 }

 private static void Recur(int i) 
 {
   Console.WriteLine(i);
   Recur(i + 1);
 }

}</lang>

Through debugging, the highest I achieve is 14250.

Through execution (with Mono), another user has reached 697186.

Clojure

<lang clojure> => (def *stack* 0) => ((fn overflow [] ((def *stack* (inc *stack*))(overflow)))) java.lang.StackOverflowError (NO_SOURCE_FILE:0) => *stack* 10498 </lang>

D

<lang d>import std.c.stdio;

void recurse(in uint i=0) {

   printf("%u ", i);
   recurse(i + 1);

}

void main() {

   recurse();

}</lang> With the DMD compiler, using default compilation arguments, the stack overflows at 51_002.

With DMD increasing the stack size using for example -L/STACK:1500000000 the stack overflows at 75_002_026.

Using -O compilation argument DMD performs tail call optimization, and the stack doesn't overflow.

Delphi

Works with: Delphi version 2010 (and probably all other versions)

<lang delphi>program Project2; {$APPTYPE CONSOLE} uses

 SysUtils;

function Recursive(Level : Integer) : Integer; begin

 try
   Level := Level + 1;
   Result := Recursive(Level);
 except
   on E: EStackOverflow do
     Result := Level;
 end;

end;

begin

 Writeln('Recursion Level is ', Recursive(0));
 Writeln('Press any key to Exit');
 Readln;

end.</lang>

Output:

Recursion Level is 28781

DWScript

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

<lang delphi>var level : Integer;

procedure Recursive; begin

  Inc(level);
  try
     Recursive;
  except
  end;

end;

Recursive;

Println('Recursion Level is ' + IntToStr(level));</lang>

E

Outside of debugging access to other vats, E programs are (ideally) not allowed to observe recursion limits, because stack unwinding at an arbitrary point can break invariants of the code that was executing at the time. In particular, consider an attacker who estimates the stack size, nearly fills up the stack to that point, then invokes the victim — If the attacker is allowed to catch our hypothetical StackOverflowException from inside the victim, then there is a good chance of the victim then being in an inconsistent state, which the attacker can then make use of.

Emacs Lisp

<lang lisp>(defun my-recurse (n)

 (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</lang>

Variable max-lisp-eval-depth[1] is the maximum depth of function calls and variable max-specpdl-size[2] is the maximum depth of nested let bindings. A function call is a let of the parameters, even if there's no parameters, and so counts towards max-specpdl-size as well as max-lisp-eval-depth.

The limits can be increased with setq etc globally, or let etc temporarily. Lisp code which knows it needs deep recursion might temporarily increase the limits. Eg. regexp-opt.el. The ultimate limit is memory or C stack.

Forth

<lang forth>: munge ( n -- n' ) 1+ recurse ;

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

test \ Default gforth: Recursion limit at depth 3817</lang>

Or you can just ask the system:

<lang forth>s" return-stack-cells" environment? ( 0 | potential-depth-of-return-stack -1 )</lang>

Full TCO is problematic, but a properly tail-recursive call is easy to add to any Forth. For example, in SwiftForth:

<lang forth>: recur; [ last 2 cells + literal ] @ +bal postpone again ; immediate

test dup if 1+ recur; then drop ." I gave up finding a limit!" ;

1 test</lang>

Fortran

<lang fortran>program recursion_depth

 implicit none

 call recurse (1)

contains

 recursive subroutine recurse (i)

   implicit none
   integer, intent (in) :: i

   write (*, '(i0)') i
   call recurse (i + 1)

 end subroutine recurse

end program recursion_depth</lang> Sample output (snipped): <lang>208914 208915 208916 208917 208918 208919 208920 208921 208922 208923 Segmentation fault (core dumped)</lang>

F#

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

<lang fsharp>let rec recurse n =

 recurse (n+1)

recurse 0</lang>

The non-tail recursive function of the following example crashed with a StackOverflowException after 39958 recursive calls:

<lang fsharp>let rec recurse n =

  printfn "%d" n
  1 + recurse (n+1)

recurse 0 |> ignore</lang>

GAP

The limit is around 5000 : <lang gap>f := function(n)

 return f(n+1);

end;

1. Now loop until an error occurs

f(0);

1. Error message :
2. Entering break read-eval-print loop ...
3. you can 'quit;' to quit to outer loop, or
4. you may 'return;' to continue

n;

1. 4998

1. quit "brk mode" and return to GAP

quit;</lang> This is the default GAP recursion trap, see reference manual, section 7.10. It enters "brk mode" after multiples of 5000 recursions levels. On can change this interval : <lang gap>SetRecursionTrapInterval(100000);

1. No limit (may crash GAP if recursion is not controlled) :

SetRecursionTrapInterval(0);</lang>

gnuplot

<lang gnuplot># Put this in a file recurse.gnuplot and run as

1. gnuplot -e try=1 recurse.gnuplot

1. probe by 1 up to 1000, then by 1% increases

try=(try<1000 ? try+1 : try*1.01)

recurse(n) = (n > 0 ? recurse(n-1) : 'ok') print "try recurse ", try print recurse(try) reread</lang>

Gnuplot 4.6 has a builtin STACK_DEPTH limit of 250, giving

try recurse 251
"/so/rosetta/recurse.gnuplot", line 2499: recursion depth limit exceeded

Gnuplot 4.4 and earlier has no limit except the C stack, giving a segv or whatever eventually.

Go

Go features stacks that grow as needed, so I expected a rather large recursion limit. I used this simple program, that prints every 1000 levels: <lang go>package main

import "fmt"

func main() {

   r(1)

}

func r(l int) {

   if l % 1000 == 0 {
       fmt.Println(l)
   }
   r(l+1)

}</lang> I tested on a smallish computer by today's standards, 1 GB RAM, and the standard Ubuntu installation gave it 2.5 GB swap. The program filled available RAM quickly, at a recursion depth of about 10M. It took a several minutes then to exhaust swap before exiting with this trace: (as you see, at a depth of over 25M.)

...
25611000
25612000
25613000
25614000
throw: out of memory (FixAlloc)

runtime.throw+0x43 /home/sonia/go/src/pkg/runtime/runtime.c:102
	runtime.throw(0x80e80c8, 0x1)
runtime.FixAlloc_Alloc+0x76 /home/sonia/go/src/pkg/runtime/mfixalloc.c:43
	runtime.FixAlloc_Alloc(0x80eb558, 0x2f)
runtime.stackalloc+0xfb /home/sonia/go/src/pkg/runtime/malloc.c:326
	runtime.stackalloc(0x1000, 0x8048c44)
runtime.newstack+0x140 /home/sonia/go/src/pkg/runtime/proc.c:768
	runtime.newstack()
runtime.morestack+0x4f /home/sonia/go/src/pkg/runtime/386/asm.s:220
	runtime.morestack()
----- morestack called from goroutine 1 -----
main.r+0x1a /home/sonia/t.go:9
	main.r(0x186d801, 0x0)
main.r+0x95 /home/sonia/t.go:13
	main.r(0x186d800, 0x0)
main.r+0x95 /home/sonia/t.go:13
	main.r(0x186d7ff, 0x0)
main.r+0x95 /home/sonia/t.go:13
	main.r(0x186d7fe, 0x0)
main.r+0x95 /home/sonia/t.go:13
	main.r(0x186d7fd, 0x0)

... (more of the same stack trace omitted)


----- goroutine created by -----
_rt0_386+0xc1 /home/sonia/go/src/pkg/runtime/386/asm.s:80

goroutine 1 [2]:
runtime.entersyscall+0x6f /home/sonia/go/src/pkg/runtime/proc.c:639
	runtime.entersyscall()
syscall.Syscall+0x53 /home/sonia/go/src/pkg/syscall/asm_linux_386.s:33
	syscall.Syscall()
syscall.Write+0x5c /home/sonia/go/src/pkg/syscall/zsyscall_linux_386.go:734
	syscall.Write(0x1, 0x977e4f18, 0x9, 0x40, 0x9, ...)
os.*File·write+0x39 /home/sonia/go/src/pkg/os/file_unix.go:115
	os.*File·write(0x0, 0x0, 0x9, 0x40, 0x9, ...)
os.*File·Write+0x98 /home/sonia/go/src/pkg/os/file.go:141
	os.*File·Write(0xbffe1980, 0x8, 0x9, 0x8048cbf, 0x186d6b4, ...)
----- goroutine created by -----
_rt0_386+0xc1 /home/sonia/go/src/pkg/runtime/386/asm.s:80

Hey, at least it terminated in a controlled way. I tried this task a few months ago and it crashed the whole computer. I read that the Go runtime has since been improved to handle out of memory conditions more gracefully. Seems so—my machine is still up.

Groovy

Translation of: Java

Solution: <lang groovy>def recurse; recurse = {

   try {
       recurse (it + 1)
   } catch (StackOverflowError e) {
       return it
   }

}

recurse(0)</lang>

Output:

387

Icon and Unicon

<lang Icon>procedure main() envar := "MSTKSIZE" write(&errout,"Program to test recursion depth - dependant on the environment variable ",envar," = ",\getenv(envar)|&null) deepdive() end

procedure deepdive() static d initial d := 0 write( d +:= 1) deepdive() end</lang> 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.

Inform 7

<lang inform7>Home is a room.

When play begins: recurse 0.

To recurse (N - number): say "[N]."; recurse N + 1.</lang>

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

J

This task assumes that all stack frames must be the same size, which is probably not the case:

 <lang J>   $:@>: ::] 0</lang>

Note also, that ^: can be used for induction, and does not have stack size limits, though it does require that the function involved is a mathematical function -- and this is not always the case (for example, Markov processes typically use non-functions).

Java

<lang Java> public class RecursionTest {

   private static void recurse(int i) {
       try {

recurse(i+1); } catch (java.lang.StackOverflowError e) { System.out.print("Recursion depth on this system is " + i + "."); }

   }

   public static void main(String[] args) {
       recurse(0);
   }

} </lang>

Sample output:

Recursion depth on this system is 10473.

Settings:

Default size of stack is 320 kB.. To extend the memory allocated for stack can be used switch -Xss with the memmory limits.
For example: java -cp . -Xss1m RecursionTest (set the stack size to 1 MB).

JavaScript

<lang javascript> function recurse(depth) {

try
{
 return recurse(depth + 1);
}
catch(ex)
{
 return depth;
}

}

var maxRecursion = recurse(1); document.write("Recursion depth on this system is " + maxRecursion);</lang>

Sample output (Chrome):

Recursion depth on this system is 10473.

Sample output (Firefox 1.6.13):

Recursion depth on this system is 3000.

Sample output (IE6):

Recursion depth on this system is 2552.

Liberty BASIC

Checks for the case of gosub & for proper subroutine. <lang lb> 'subroutine recursion limit- end up on 475000

call test 1

sub test n

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

end sub </lang>

<lang lb> 'gosub recursion limit- end up on 5767000 [test]

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

gosub [test] </lang>

Logo

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.

<lang logo>make "depth 0

to recurse

 make "depth :depth + 1
 recurse

end

catch "ERROR [recurse]

 ; hit control-C after waiting a while

print error  ; 16 Stopping... recurse [make "depth :depth + 1] (print [Depth reached:] :depth)  ; some arbitrarily large number</lang>

Lua

<lang Lua> counter = 0

function test()

  print("Depth:", counter)
  counter = counter + 1
  test()

end

test() </lang>

LSL

I ran this twice and got 1891 and 1890; probably varies with the number Avatars on a Sim and other variables I can't control.

Originally I had it without the OwnerSay in the recursive function. Generally, if LSL has a Runtime Error it just shouts on the DEBUG_CHANNEL and skips to the next statement (which would have returned to the next statement in state_entry() said the highest number it had achieved) but, it just shouted "Script run-time error. Object: Stack-Heap Collision" on debug and quit running.

To test it yourself; rez a box on the ground, and add the following as a New Script. <lang LSL>integer iLimit_of_Recursion = 0; Find_Limit_of_Recursion(integer x) { llOwnerSay("x="+(string)x); iLimit_of_Recursion = x; Find_Limit_of_Recursion(x+1); } default { state_entry() { Find_Limit_of_Recursion(0); llOwnerSay("iLimit_of_Recursion="+(string)iLimit_of_Recursion); } } </lang> Output:

[2012/07/07 18:40]  Object: x=0
[2012/07/07 18:40]  Object: x=1
[2012/07/07 18:40]  Object: x=2
   ...   ...   ...   ...   ...
[2012/07/07 18:41]  Object: x=1888
[2012/07/07 18:41]  Object: x=1889
[2012/07/07 18:41]  Object: x=1890
[2012/07/07 18:41]  Object: Object [script:New Script] Script run-time error
[2012/07/07 18:41]  Object: Stack-Heap Collision

Mathematica

The variable $RecursionLimit can be read for its current value or set to different values. eg <lang>$RecursionLimit=10^6</lang> Would set the recursion limit to one million.

MATLAB

The recursion limit can be 'get' and 'set' using the "get" and "set" keywords.

Sample Usage: <lang MATLAB>>> get(0,'RecursionLimit')

ans =

  500

>> set(0,'RecursionLimit',2500) >> get(0,'RecursionLimit')

ans =

       2500</lang>

Maxima

<lang maxima>f(p) := f(n: p + 1)$ f(0); Maxima encountered a Lisp error:

Error in PROGN [or a callee]: Bind stack overflow.

Automatically continuing. To enable the Lisp debugger set *debugger-hook* to nil.

n; 406</lang>

MUMPS

<lang MUMPS>RECURSE

IF $DATA(DEPTH)=1 SET DEPTH=1+DEPTH
IF $DATA(DEPTH)=0 SET DEPTH=1
WRITE !,DEPTH_" levels down"
DO RECURSE
QUIT</lang>

End of the run ...

1918 levels down
1919 levels down
1920 levels down
 DO RECURSE
 ^
<FRAMESTACK>RECURSE+4^ROSETTA
USER 72d0>

Modula-2

<lang modula2>MODULE recur;

IMPORT InOut;

PROCEDURE recursion (a : CARDINAL);

BEGIN

 InOut.Write ('.');    (*  just count the dots....     *)
 recursion (a + 1)

END recursion;

BEGIN

 recursion (0)

END recur.</lang> Producing this: <lang Modula-2> jan@Beryllium:~/modula/rosetta$ recur >testfile Segmentation fault jan@Beryllium:~/modula/rosetta$ ls -l -rwxr-xr-x 1 jan users 20032 2011-05-20 00:26 recur* -rw-r--r-- 1 jan users 194 2011-05-20 00:26 recur.mod -rw-r--r-- 1 jan users 523264 2011-05-20 00:26 testfile jan@Beryllium:~/modula/rosetta$ wc testfile

    0      1 523264 testfile</lang>

So the recursion depth is just over half a million.

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. <lang NetRexx>/* NetRexx */ options replace format comments java crossref symbols binary

import java.lang.management.

memoryInfo() digDeeper(0)

/**

* Just keep digging
* @param level depth gauge
*/

method digDeeper(level = int) private static binary

 do
   digDeeper(level + 1)
 catch ex = Error
   System.out.println('Recursion got' level 'levels deep on this system.')
   System.out.println('Recursion stopped by' ex.getClass.getName())
 end
 return

/**

* Display some memory usage from the JVM
* @see ManagementFactory
* @see MemoryMXBean
* @see MemoryUsage
*/

method memoryInfo() private static

 mxBean = ManagementFactory.getMemoryMXBean()   -- get the MemoryMXBean
 hmMemoryUsage = mxBean.getHeapMemoryUsage()    -- get the heap MemoryUsage object
 nmMemoryUsage = mxBean.getNonHeapMemoryUsage() -- get the non-heap MemoryUsage object
 say 'JVM Memory Information:'
 say '      Heap:' hmMemoryUsage.toString()
 say '  Non-Heap:' nmMemoryUsage.toString()
 say '-'.left(120, '-')
 say
 return

</lang> Output:

JVM Memory Information: 
      Heap: init = 0(0K) used = 2096040(2046K) committed = 85000192(83008K) max = 129957888(126912K) 
  Non-Heap: init = 24317952(23748K) used = 5375328(5249K) committed = 24317952(23748K) max = 136314880(133120K) 
------------------------------------------------------------------------------------------------------------------------ 
 
Recursion got 9673 levels deep on this system. 
Recursion stopped by java.lang.StackOverflowError 

OCaml

When the recursion is a "tail-recursion" there is no limit. Which is important because being a functional programming language, OCaml uses recursion to make loops.

If the recursion is not a tail one, the execution is stopped with the message "Stack overflow": <lang ocaml># let last = ref 0 ;; val last : int ref = {contents = 0}

1. let rec f i =

   last := i;
   i + (f (i+1))
 ;;

val f : int -> int = <fun>

1. f 0 ;;

stack overflow during evaluation (looping recursion?).

1. !last ;;

- : int = 262067</lang>

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

<lang ocaml>(* One can build a function from the idea above, catching the exception *)

let rec_limit () = let last = ref 0 in let rec f i = last := i; 1 + f (i + 1) in try (f 0) with Stack_overflow -> !last;;

rec_limit ();; 262064

(* 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 *)</lang>

ooRexx

Using ooRexx for the program shown under Rexx:

 rexx pgm 1>x1 2>x2

 puts the numbers in x1 and the error messages in x2

...
2785
2786
8 *-*      call self
....
     8 *-*   call self
     3 *-* call self
Error 11 running C:\work.ooRexx\wc\main.4.1.1.release\Win32Rel\StreamClasses.orx line 366:  Control stack full
Error 11.1:  Insufficient control stack space; cannot continue execution

Oz

Translation of: Scheme

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 Number will slowly increase): <lang oz>declare

 proc {Recurse Number}
    {Show Number}
    {Recurse Number+1}
 end

in

 {Recurse 1}</lang>

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

PARI/GP

From the documentation: <lang parigp>dive(n) = dive(n+1) dive(0)</lang>

Pascal

See Delphi

Perl

Maximum recursion depth is memory dependent.

<lang perl>my $x = 0; recurse($x);

sub recurse ($x) {

  print ++$x,"\n";
  recurse($x);

}</lang>

1
2
...
...
10702178
10702179
Out of memory!

Perl 6

Maximum recursion in Perl 6 is implementation dependent and subject to change as development proceeds.

<lang perl6>my $x = 0; recurse;

sub recurse () {

  say ++$x;
  recurse;

}</lang> Using Rakudo 2011.01 this yields:

1
2
...
...
971
972
maximum recursion depth exceeded

This is because the Parrot VM currently imposes a limit of 1000. On the other hand, the niecza implementation has no limit, subject to availability of virtual memory. In any case, future Perl 6 is likely to require tail call elimination in the absence of some declaration to the contrary.

PicoLisp

The 64-bit and the 32-bit version behave slightly different. While the 32-bit version imposes no limit on its own, and relies on the 'ulimit' setting of the caller, the 64-bit version segments the available stack (likewise depending on 'ulimit') and allows each (co)routine a maximal stack size as configured by 'stack'.

32-bit version

$ ulimit -s
8192
$ pil +
: (let N 0 (recur (N) (recurse (msg (inc N)))))
...
730395
730396
730397
Segmentation fault

64-bit version

$ ulimit -s
unlimited
$ pil +
: (stack)  # The default stack segment size is 4 MB
-> 4

: (co 'a (yield 7))  # Start a dummy coroutine
-> 7

: (let N 0 (recur (N) (recurse (println (inc N)))))
...
43642
43643
43644
Stack overflow
?

PHP

<lang PHP><?php function a() {

   static $i = 0;
   print ++$i . "\n";
   a();

} a();</lang>

Sample output:

1
2
3
[...]
597354
597355
597356
597357
597358

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 261904 bytes) in [script-location.php] on line 5

PL/I

<lang PL/I> recurs: proc options (main) reorder; dcl sysprint file; dcl mod builtin;

dcl ri fixed bin(31) init (0);

recursive: proc recursive;

 ri += 1;
 if mod(ri, 1024) = 1 then
   put data(ri);

 call recursive();

end recursive;

call recursive(); end recurs; </lang>

Result (abbreviated):

...
RI=       4894721;
RI=       4895745;
RI=       4896769;
RI=       4897793;
RI=       4898817;

At this stage the program, running on z/OS with a REGION=0M on the EXEC statement (i.e. grab as much storage as you like), ABENDs with a USER COMPLETION CODE=4088 REASON CODE=000003EC

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

PowerShell

Both of these examples will throw an exception when the recursion depth is exceeded, however, the exception cannot be trapped in the script. The exception thrown on a Windows 2008 x64 system is

<lang>The script failed due to call depth overflow. The call depth reached 1001 and the maximum is 1000. System.Management.Automation</lang>

PowerShell v1.0 Example

<lang PowerShell>function Check-Recursion{

  trap [Exception] {
     Write-Host $_.Exception.Message
  }
  Check-Recursion

}

trap [Exception] {

 Write-Host $_.Exception.Message

} Check-Recursion</lang>

PowerShell V2.0+ Example

<lang PowerShell>function Check-Recursion{

   Check-Recursion

}

try { Check-Recursion } catch { Write-Host $_.Exception.Message }</lang>

PureBasic

The recursion limit is primarily determined by the stack size. The stack size can be changed when compiling a program by specifying the new size using '/stack:NewSize' in the linker file.

Procedural

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. <lang PureBasic>Procedure Recur(n)

 PrintN(str(n))
 Recur(n+1)

EndProcedure

Recur(1)</lang>

Stack overflow after 86317 recursions on x86 Vista.

Classic

<lang PureBasic>rec:

 PrintN(str(n))
 n+1
 Gosub rec
 Return</lang>
Stack overflow after 258931 recursions on x86 Vista.

Python

<lang python>import sys print sys.getrecursionlimit()</lang> To set it: <lang python>import sys sys.setrecursionlimit(12345)</lang>

R

R's recursion is counted by the number of expressions to be evaluated, rather than the number of function calls. <lang r>#Get the limit options("expressions")

1. Set it

options(expressions = 10000)

1. Test it

recurse <- function(x) {

 print(x)
 recurse(x+1)

} recurse(0)</lang>

Retro

When run, this will display the address stack depth until it reaches the max depth. Once the address stack is full, Retro will crash.

<lang Retro>: try -6 5 out wait 5 in putn cr try ;</lang>

REXX

recursive procedure

On (IBM's) VM/CMS, the limit of recursion was built-into CMS to stop run-away EXEC programs (this
included EXEC[0], EXEC2, and REXX) being called recursively, it was either 200 or 250 as I recall.
This limit was maybe changed later to allow the user to specify the limit. My memory is really fuzzy about these details. <lang rexx>/*REXX pgm finds the recursion limit: a subroutine that calls itself. */ parse version x; say x; say n=0 call SELF 1 exit /*this statement will never be executed.*/ /*───────────────────────────SELF procedure─────────────────────────────*/ self: procedure expose n n=n+1 say n call self</lang> output using Regina 3.6 under Windows/XP Pro

REXX-Regina_3.6(MT) 5.00 31 Dec 2011
 .
 .
 .
164423
164424
164425
164426
164427
164428
164429
164430
164431
System resources exhausted

[Your mileage will vary.]

Note that the above recursion limit will be less and it's dependant upon how much virtual memory the program itself uses,
this would include REXX variables and their values, and the program source (as it's kept in virtual memory also),
and the size of the REXX.EXE and REXX.DLL programs, and any other programs executing in the Windows DOS (including
either the CMD.EXE or COMMAND.COM) shell).

output using Personal REXX under Windows/XP Pro
The recursion level wasn't captured, but the last number shown was 240.

REXX/Personal 4.00 21 Mar 1992
 .
 .
 .
    10 +++ call self
    10 +++ call self
    10 +++ call self
    10 +++ call self
    10 +++ call self
    10 +++ call self
    10 +++ call self
    10 +++ call self
    10 +++ call self
     4 +++ call SELF 1
Error 5 on line 10 of D:\SELF.REX: Machine resources exhausted

output using R4 REXX under Windows/XP Pro

REXX-r4 4.00 29 Apr 2012
 .
 .
 .
499
500
501
502
503
504
505
506
507
An unexpected error occurred

output using ROO REXX under Windows/XP Pro

REXX-roo 4.00 28 Jan 2007

 .
 .
 .
374
375
376
377
378
379
380
381
382
An unexpected error occurred

recursive subroutine

<lang rexx>/*REXX pgm finds the recursion limit: a subroutine that calls itself. */ parse version x; say x; say n=0 call SELF 2 exit /*this statement will never be executed.*/ /*───────────────────────────SELF subroutine────────────────────────────*/ self: n=n+1 say n call self</lang> output (paraphrased and edited)

For Regina 3.6,     it was 828,441.
For Personnal REXX, it was 240  (the same).
For R4,             it was 507  (the same).
For ROO,            it was 382  (the same).

Ruby

<lang ruby>def recurse x

   puts x
   recurse(x+1)

end

recurse(0)</lang> Produces a SystemStackError:

.
.
.
6074
recurse.rb:3:in `recurse': stack level too deep (SystemStackError)
	from recurse.rb:3:in `recurse'
	from recurse.rb:6

Sather

<lang sather>class MAIN is

 attr r:INT;
 recurse is
   r := r + 1;
   #OUT + r + "\n";
   recurse;
 end;
 main is
   r := 0;
   recurse;
 end;

end;</lang>

Segmentation fault is reached when r is 130560.

Scala

<lang scala>def recurseTest(i:Int):Unit={

  try{
     recurseTest(i+1)
  } catch { case e:java.lang.StackOverflowError => 
     println("Recursion depth on this system is " + i + ".")
  }

} recurseTest(0)</lang> You'll get an output like this, depending on the current stack size.

Recursion depth on this system is 4869.

If your function is tail-recursive the compiler transforms it into a loop. <lang scala>def recurseTailRec(i:Int):Unit={

  if(i%100000==0) println("Recursion depth is " + i + ".")
  recurseTailRec(i+1)

}</lang>

Scheme

<lang scheme>(define (recurse number)

 (begin (display number) (newline) (recurse (+ number 1))))

(recurse 1)</lang> 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.

Tcl

<lang tcl>proc recur i {

   puts "This is depth [incr i]"
   catch {recur $i}; # Trap error from going too deep

} recur 0</lang> The tail of the execution trace looks like this:

This is depth 995
This is depth 996
This is depth 997
This is depth 998
This is depth 999

Note that the maximum recursion depth is a tunable parameter, as is shown in this program: <lang tcl># Increase the maximum depth interp recursionlimit {} 1000000 proc recur i {

   if {[catch {recur [incr i]}]} {
       # If we failed to recurse, print how far we got

puts "Got to depth $i"

   }

} recur 0</lang> For Tcl 8.5 on this platform, this prints:

Got to depth 6610

At which point it has exhausted the C stack, a trapped error. Tcl 8.6 uses a stackless execution engine, and can go very deep if required:

Got to depth 999999

TSE SAL

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

Message( I )
PROCProgramRunRecursionLimit( I + 1 )

END

PROC Main()

PROCProgramRunRecursionLimit( 1 )

END </lang>

UNIX Shell

Works with: Bourne Again SHell

<lang bash>recurse() {

 # since the example runs slowly, the following
 # if-elif avoid unuseful output; the elif was
 # added after a first run ended with a segmentation
 # fault after printing "10000"
 if $(($1 % 5000)) -eq 0 ; then 
     echo $1;
 elif $1 -gt 10000 ; then
     echo $1
 fi
 recurse $(($1 + 1))

}

recurse 0</lang>

The Bash reference manual says No limit is placed on the number of recursive calls, nonetheless a segmentation fault occurs at 13777 (Bash v3.2.19 on 32bit GNU/Linux)

VBScript

Haven't figured out how to see the depth. And this depth is that of calling the O/S rather than calling within.

<lang vb>'mung.vbs option explicit

dim c if wscript.arguments.count = 1 then c = wscript.arguments(0) c = c + 1 else c = 0 end if wscript.echo "[Depth",c & "] Mung until no good." CreateObject("WScript.Shell").Run "cscript Mung.vbs " & c, 1, true wscript.echo "[Depth",c & "] no good."</lang>

Okay, the internal limits version.

<lang vb>'mung.vbs option explicit

sub mung(c) dim n n=c+1 wscript.echo "[Level",n & "] Mung until no good" on error resume next mung n on error goto 0 wscript.echo "[Level",n & "] no good" end sub

mung 0</lang>

Output (abbrev.):

[Level 1719] Mung until no good
[Level 1720] Mung until no good
[Level 1721] Mung until no good
[Level 1722] Mung until no good
[Level 1722] no good
[Level 1721] no good
[Level 1720] no good
[Level 1719] no good

x86 Assembly

Works with: nasm

<lang asm> global main

  section .text

main xor eax, eax call recurse ret

recurse add eax, 1 call recurse ret</lang>

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