Find limit of recursion: Difference between revisions
(C) |
m (→{{header|C}}) |
||
Line 83: | Line 83: | ||
}</lang> |
}</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 <code>recurse</code>, the limit is reached at <code>i == 261803</code>. The limit depends on the stack size. |
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; so if each call to the function uses more stack space, the recursion limit becomes smaller. |
||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 10:45, 20 April 2010
You are encouraged to solve this task according to the task description, using any language you may know.
Find the limit of recursion.
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; so if each call to the function uses more stack space, the recursion limit becomes smaller.
Python
<lang python>import sys print sys.getrecursionlimit()</lang>
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. Tcl 8.6 uses a stackless execution engine, and can go very deep if required:
Got to depth 999999
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