Find limit of recursion: Difference between revisions

Line 1:

{{task}}{{selection|Short Circuit|Console Program Basics}}[[Category:Basic language learning]][[Category:Programming environment operations]]~~Find~~ ~~the limit of recursion.~~

{{task}}{{selection|Short Circuit|Console Program Basics}}[[Category:Basic language learning]][[Category:Programming environment operations]] [[Category:Simple]]

Find the limit of recursion.

=={{header|ACL2}}==

Line 8:

Line 9:

(1+ (recursion-limit (1+ x))))))</lang>

~~Output~~ (trimmed):

{{out}} (trimmed):

<pre>87195

87196

Line 47:

Line 48:

In real-life Storage_Error is usually fatal.

Sample output:

<pre>

Recursion depth on this system is 524091

Line 173:

Line 174:

</lang>

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

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

{{{

Recursion depth: 13792

Line 187:

Line 188:

PROCrecurse(depth% + 1)

ENDPROC</lang>

~~Output~~ from BBC BASIC for Windows with default value of HIMEM:

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

<pre>

37400

Line 217:

Line 218:

}</lang>

Segmentation fault occurs when i is 523756.

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 <code>recurse</code>, the limit is reached at <code>i == 261803</code>. 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.

(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 <code>recurse</code>, the limit is reached at <code>i == 261803</code>.

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:

Line 376:

Line 383:

</lang>

~~Example~~ ~~output~~ on [http://nodejs.org Node.js]:

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

<pre>

Recursion depth on this system is 9668

</pre>

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

Line 388:

Line 396:

</lang>

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

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

<pre>

3056. Trace: (RECURSE)

3057. Trace: (RECURSE)

Line 395:

Line 404:

*** - Lisp stack overflow. RESET

</pre>

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

However, for an implementation of Lisp that supports proper tail recursion,

this function will not cause a stack overflow, so this method will not work.

=={{header|C sharp|C#}}==

Line 468:

Line 479:

end.</lang>

Output:

<pre>Recursion Level is 28781</pre>

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

Line 477:

Line 489:

rec-fun 0</lang>

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. Eliminating the <code>n</code> should give over 10 million levels on the same machine.~~

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.

Eliminating the <code>n</code> should give over 10 million levels on the same machine.

=={{header|DWScript}}==

Line 556:

Line 570:

end program recursion_depth</lang>

~~Sample output~~ (snipped):

{{out}} (snipped):

<~~lang~~>208914

<pre>208914

208915

208916

Line 567:

Line 581:

208922

208923

Segmentation fault (core dumped)</~~lang~~>

Segmentation fault (core dumped)</pre>

Line 801:

Line 815:

recurse(0)</lang>

Output:

Line 859:

Line 873:

</lang>

Sample output:

<pre>Recursion depth on this system is 10473.</pre>

Line 883:

Line 897:

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

~~Sample output~~ (Chrome):

{{out}} (Chrome):

<pre>Recursion depth on this system is 10473.</pre>

~~Sample output~~ (Firefox 1.6.13):

{{out}} (Firefox 1.6.13):

<pre>Recursion depth on this system is 3000.</pre>

~~Sample output~~ (IE6):

{{out}} (IE6):

<pre>Recursion depth on this system is 2552.</pre>

Line 1,036:

Line 1,050:

}

</lang>

Output:

<pre>

[2012/07/07 18:40] Object: x=0

Line 1,171:

Line 1,185:

return

</lang>

'''Output:'''

<pre>

JVM Memory Information:

Line 1,358:

Line 1,372:

a();</lang>

Sample output:

<pre>

1

2

Line 1,370:

Line 1,385:

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

</pre>

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

Line 1,508:

Line 1,524:

say n

call self</lang>

~~'''output'''~~ using Regina 3.6 under Windows/XP Pro

{{out}} using Regina 3.6 under Windows/XP Pro

REXX-Regina_3.6(MT) 5.00 31 Dec 2011

Line 1,531:

Line 1,547:

either the CMD.EXE or COMMAND.COM) shell).

~~'''output'''~~ using Personal REXX under Windows/XP Pro

{{out}} using Personal REXX under Windows/XP Pro

~~ ~~The recursion level wasn't captured, but the last number shown was 240.

The recursion level wasn't captured, but the last number shown was 240.

REXX/Personal 4.00 21 Mar 1992

Line 1,550:

Line 1,566:

Error 5 on line 10 of D:\SELF.REX: Machine resources exhausted

</pre>

~~'''output'''~~ using R4 REXX under Windows/XP Pro

{{out}} using R4 REXX under Windows/XP Pro

REXX-r4 4.00 29 Apr 2012

Line 1,567:

Line 1,583:

An unexpected error occurred

</pre>

~~'''output'''~~ using ROO REXX under Windows/XP Pro

{{out}} using ROO REXX under Windows/XP Pro

REXX-roo 4.00 28 Jan 2007

Line 1,585:

Line 1,601:

An unexpected error occurred

</pre>

~~'''output'''~~ using ooRexx under Windows/7

{{out}} using ooRexx under Windows/7

<pre>See section ooRexx</pre>

Line 1,600:

Line 1,616:

say n

call self</lang>

~~'''output'''~~ (paraphrased and edited)

{{out}} (paraphrased and edited)

<pre>

For Regina 3.7, it was 828,441.

Line 1,620:

Line 1,636:

recurse(0)</lang>

Produces a SystemStackError:

{{out}} Produces a SystemStackError:

<pre>

.

Line 1,722:

Line 1,737:

}

recurseTest(0)</lang>

~~You'll get an output like this,~~ depending on the current stack size.

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

Line 1,898:

Line 1,913:

mung 0</lang>

~~Output~~ (abbrev.):

{{out}} (abbrev.):

<pre>[Level 1719] Mung until no good

[Level 1720] Mung until no good