Find limit of recursion: Difference between revisions
m (→{{header|PureBasic}}: updated with gosub version) |
m (moved Find Limit of Recursion to Find limit of recursion: Author request) |
(No difference)
|
Revision as of 15:25, 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 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> static void Main(string[] args) {
Recur(0); Console.Read();
}
private static void Recur(int i) {
Console.WriteLine(i); Recur(i + 1);
}</lang>
Through debugging, the highest I achieve is 14250.
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> Output (snipped): <lang>208914 208915 208916 208917 208918 208919 208920 208921 208922 208923 Segmentation fault (core dumped)</lang>
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>
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.
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
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
<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.