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.

AutoHotkey

<lang AutoHotkey>Recurse(0)

Recurse(x) {

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

}</lang>

Last visible number is 827.

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>

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.

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.

D

<lang d>import std.c.stdio: printf;

void recurse(uint i=0) {

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

}

void main() {

   recurse();

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

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

DMD also allows to increase the stack size. Using for example -L/STACK:1500000000 the stack overflows at 75_002_026.

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.

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>

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>

Icon and Unicon

Icon

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

Unicon

This Icon solution works in Unicon.

J

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

 <lang J>   $:@>:@]@(1!:2&2)1</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).

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>

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.

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.

PureBasic

Procedural <lang PureBasic>Procedure Recur(n)

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

EndProcedure

Recur(1)</lang>

Stack overflow after 86317 recursions on x86 Vista.

Classic way <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>

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.

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

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.