17
\$\begingroup\$

Does your language have a maximum recursion depth (MRD)?

Let's say your language has MRD=500

Write a code that finds the recursion depth and outputs the exact value

For the case above your program (or function) should output 500

Code-Golf Shortest answer wins!

\$\endgroup\$
16
  • 4
    \$\begingroup\$ @cairdcoinheringaahing ..."that finds the recursion depth" means hardcoding is invalid \$\endgroup\$
    – user72269
    Aug 31 '17 at 23:33
  • 9
    \$\begingroup\$ I think the main problem with this challenge is that printing a hardcoded value is not allowed, but reading a hardcoded system variable is fine. The two don't really seem significantly different to me. \$\endgroup\$
    – DJMcMayhem
    Aug 31 '17 at 23:44
  • 2
    \$\begingroup\$ @DJMcMayhem built-ins many times use hardcoded information. This challenge allows built-ins. \$\endgroup\$
    – user72269
    Aug 31 '17 at 23:48
  • 7
    \$\begingroup\$ Yes, that's my point. They're both simply reading a hardcoded value, but one is allowed and the other isn't. \$\endgroup\$
    – DJMcMayhem
    Aug 31 '17 at 23:49
  • 3
    \$\begingroup\$ @DJMcMayhem built-in in mathematica can also have the swiss flag (I have seen this challenge here), but posting the same flag as jpg is invalid. \$\endgroup\$
    – user72269
    Aug 31 '17 at 23:53

24 Answers 24

53
\$\begingroup\$

Mathematica, 15 bytes

$RecursionLimit

¯\_(ツ)_/¯

Try it online!

\$\endgroup\$
3
  • 19
    \$\begingroup\$ Of course Mathematica has a built in for this! +1 \$\endgroup\$ Aug 31 '17 at 23:26
  • 2
    \$\begingroup\$ Gotta love Mathematica +1 \$\endgroup\$ Sep 1 '17 at 4:36
  • 1
    \$\begingroup\$ Emacs Lisp in the same vein (19): max-lisp-eval-depth \$\endgroup\$ Sep 1 '17 at 17:28
21
\$\begingroup\$

Python 3, 40 bytes

def f(x=2):
 try:f(x+1)
 except:print(x)

Try it online!

Without just reading it from the builtin. We start at 2 instead of 1 because the except clause is run one level before it errors. This is a byte shorter in python 2, of course.

\$\endgroup\$
0
15
\$\begingroup\$

Mathematica (no built-in), 20 bytes

#0[#+1];&@1
%[[1,1]]

Omitting the ; will calculate 1+$IterationLimit (probably because Mathematica tail-optimize the function). Alternatively 0 //. x_ -> x + 1 calculate ReplaceRepeated's default MaxIteration, that is, 65536 (which is larger than both value above).

(This is a code snippet which evaluates to the result. However the other Mathematica solution is also)

\$\endgroup\$
0
15
\$\begingroup\$

JavaScript (Babel), 35 33 29 bytes

f=_=>do{try{-~f()}catch(e){}}
  • 2 bytes saved thanks to Neil.

Try it here, or use the Snippet below to test it with eval instead of do.

console.log((f=_=>eval(`try{-~f()}catch(e){}`))())


Japt port, 24 bytes

It's not really worth posting this as a separate solution as it's, essentially, identical.

Ox`try\{-~rp()}¯t®(e)\{}

Test it


Explanation

JavaScript itself doesn't have a recursion limit per se, rather the limit is imposed by the interpreter (i.e., the browser) - good thing we define languages by their interpreter 'round here! Among other factors, the limit can vary by browser and available memory, which is impacted by the operations being performed. The following Snippet illustrates that last point, using the 5 different versions of this solution I went through. As you can see from the last 2 tests, in Chrome, at least, even the order of operations can make a difference.

console.log((f=(i=0)=>eval(`try{f(i+1)}catch(e){i}`))())
console.log((f=i=>eval(`try{f(-~i)}catch(e){i}`))())
console.log((f=(i=0)=>eval(`try{f(++i)}catch(e){i}`))())
console.log((f=_=>eval(`try{-~f()}catch(e){}`))())
console.log((f=_=>eval(`try{f()+1}catch(e){0}`))())
console.log((f=_=>eval(`try{1+f()}catch(e){0}`))())

Given that, we therefore don't have the convenience of a constant or method to work with. Instead, we're going to create a function that calls itself continuously before, eventually, crapping out. In it's simplest form that is:

f=_=>f()

But that's not much use to us for this challenge as it only throws an overflow error with no indication of how many times f called itself. We can avoid the error by trying to call f continuously and catching when it fails:

f=_=>{try{f()}catch(e){}}

No error, but still no return value of how many times the function managed to call itself before failing, because the catch isn't actually doing anything. Let's try evaluating the try / catch statement:

f=_=>eval(`try{f()}catch(e){}`)

Now we've got a value being returned (and, because this is code golf, saved ourselves a few bytes over using an actual return). The value being returned, though, is undefined, again because the catch isn't doing anything. Luckily for us -~undefined==1 and -~n==n+1 so, by popping a -~ in front of the call to f, we've essentially got -~-~ ... -~-~undefined, with another -~ prepended with each call, giving us the number of times f was called.

f=_=>eval(`try{-~f()}catch(e){}`)
\$\endgroup\$
3
  • \$\begingroup\$ Nice solution, since I'm assuming you don't have access to a recursion depth builtin in JS! \$\endgroup\$
    – Adalynn
    Aug 31 '17 at 23:55
  • 3
    \$\begingroup\$ 33 bytes: f=_=>eval('try{-~f()}catch(e){}') \$\endgroup\$
    – Neil
    Aug 31 '17 at 23:57
  • \$\begingroup\$ @Neil: I saw your 34 byte version as I was going to bed and kicked myself for not thinking of it. That 33 byte version is inspired. Thanks. \$\endgroup\$
    – Shaggy
    Sep 1 '17 at 7:21
10
\$\begingroup\$

J, 8 bytes

1+$: ::]

Try it online!

So, I don't actually know how to execute a verb without any input and some brief searching (as well as personal intuition) makes it seem like that isn't possible. If it is, please let me know how to do it and I'll either delete or update my answer. It doesn't really make sense for a verb to be given no input, though. In light of this, the function given expects 0, the default "empty" input for integers. I can probably change it to use the empty array (0$0) if you think that's more befitting.

Edit: the OP has allowed the function to take 0.

Explanation

1+$: ::]
     ::]  Assign adverse: if an error occurs, call ] (the identify function)
1+        Add one to
  $:      Recursive call to self

This calls itself recursively, adding 1 to the input (0 expected) until it hits a stack error. When it errors, it calls the adverse (]-right identity) on the input, which is just 0.

By the way, the space is necessary.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ outputs 6000 on my machine. fwiw i think this should be fair game, but you can always just make your answer (1+$: ::]) 0 \$\endgroup\$
    – Jonah
    Sep 1 '17 at 0:12
  • \$\begingroup\$ @Jonah fair point, I'm used to submitting functions. On my machine, it's 6666 oddly enough. \$\endgroup\$
    – cole
    Sep 1 '17 at 0:22
  • \$\begingroup\$ 6660 on an iPad pro. Cool! \$\endgroup\$
    – Aganju
    Sep 1 '17 at 14:14
  • \$\begingroup\$ The way it handles maximum recursion depth seems version dependent -- on my phone I get 5999 (which appears to be off by 1). On my iPad (honestly I don't remember which model), it just crashes. \$\endgroup\$
    – cole
    Sep 1 '17 at 14:22
9
\$\begingroup\$

Python 3, 41 32 bytes

import sys
sys.getrecursionlimit

Try it online!

Saved 9 bytes thanks to @FryAmTheEggman!

34 bytes

from sys import*
getrecursionlimit

35 bytes

__import__('sys').getrecursionlimit

The last 2 are thanks to @totallyhuman

\$\endgroup\$
4
  • \$\begingroup\$ 32 bytes, 34 bytes and 35 bytes. Take your pick. :P \$\endgroup\$ Sep 1 '17 at 0:14
  • \$\begingroup\$ @FryAmTheEggman yes I can, thank you! \$\endgroup\$ Sep 1 '17 at 0:15
  • \$\begingroup\$ I'm getting an error (on TIO, at least) when trying to run the first 2. \$\endgroup\$
    – Shaggy
    Sep 1 '17 at 12:32
  • \$\begingroup\$ @Shaggy you'll have to swap the lines for the first one, the import goes after in order to allow the builtin to be allocated a name. I'll update the link. \$\endgroup\$ Sep 1 '17 at 12:35
8
\$\begingroup\$

Java 8, 131 51 48 47 43 bytes

int d;int c(){try{c();}finally{return++d;}}

-80 bytes thanks to @Nevay. I tried a method instead of program as well, but made a mistake so ended up with a full program.. Now it's a method.
-3 bytes thanks to @Neil by making use of finally instead of catch(Error e).
-5 byte thanks to @Nevay again.

Explanation:

Try it here.

int d;                 // Depth-integer `d` on class-level (implicit 0)
int c(){               // Method without parameter and integer return-type
  try{c();}            //  Recursive call
  finally{return++d;}  //  Increase depth-integer `d` and always return it,
                       //   whether a StackOverflowError occurs or not
}                      // End of method
\$\endgroup\$
8
  • 1
    \$\begingroup\$ 51 bytes: int c(){try{return-~c();}catch(Error e){return 1;}} \$\endgroup\$
    – Nevay
    Sep 1 '17 at 7:57
  • 3
    \$\begingroup\$ @Nevay You often post excellent answers in comments. You could post them as answers, and get some reputations. Nothing forbids any question from having several Java answers. ;-) \$\endgroup\$ Sep 1 '17 at 9:49
  • 2
    \$\begingroup\$ int c(){int n=1;try{n=-~c();}finally{return n;}} saves 3 bytes but gives me a different answer? \$\endgroup\$
    – Neil
    Sep 1 '17 at 9:56
  • 2
    \$\begingroup\$ 47 bytes: int c(){int n=1;try{n+=c();}finally{return n;}} \$\endgroup\$
    – Nevay
    Sep 1 '17 at 10:30
  • 1
    \$\begingroup\$ 43 bytes: int d;int c(){try{c();}finally{return++d;}} \$\endgroup\$
    – Nevay
    Sep 1 '17 at 17:59
8
\$\begingroup\$

C (gcc, Linux x64), 180 133 bytes

-4 bytes thanks to @scottinet

c;f(){f(++c);}h(){exit(printf("%d",c));}main(){int b[512];f(sigaction(11,(int*[]){h,[17]=1<<27},sigaltstack((int*[]){b,0,2048},0)));}

Try it online!

Installs a SIGSEGV (signal 11) handler with an alternate signal stack (minimum size MINSIGSTKSZ is 2 KB, flag SA_ONSTACK is 0x08000000), then calls a function without arguments and no local variables recursively until the stack overflows. It's interesting that the maximum recursion depth varies across runs, probably due to ASLR.

The maximum recursion depth in C depends on a lot of factors, of course. On a typical 64-bit Linux system the default stack size is 8 MB, and the stack alignment is 16 bytes, so you get a recursion depth of about 512K for simple functions.

Also note that the program above doesn't work with -O2 because of tail call optimization.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ +1! You can save 4 bytes by incrementing c and calling exit and sigaction as parameters. This doesn't make a noticable difference on the result: TIO link \$\endgroup\$
    – scottinet
    Sep 2 '17 at 6:30
4
\$\begingroup\$

Octave, 19 bytes

max_recursion_depth

Usage:

octave:1> max_recursion_depth
ans =  256
\$\endgroup\$
4
\$\begingroup\$

R, 32 26 18 bytes

-8 bytes thanks to Sven Hohenstein : $ will do partial matching, so we can just use exp instead of the full expressions.

cat(options()$exp)

The options command can also be used to set the recursion depth, i.e., options(expressions=500) for 500.

Try it online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You can save seven bytes by removing ressions due to partial matching with $. \$\endgroup\$ Sep 1 '17 at 5:36
  • 1
    \$\begingroup\$ More for future reference than as a contribution; is the consensus that you need to wrap this in cat()? R will output something in most circumstances, so is there a post somewhere clarifying good practice/logic to follow? \$\endgroup\$ Sep 1 '17 at 8:00
  • \$\begingroup\$ @SvenHohenstein dang, I always forget about that after I write R code in good style...Thank you! \$\endgroup\$
    – Giuseppe
    Sep 1 '17 at 13:03
  • 1
    \$\begingroup\$ @CriminallyVulgar see for instance this post in meta; there's certainly some uncertainty about it. \$\endgroup\$
    – Giuseppe
    Sep 1 '17 at 13:14
4
\$\begingroup\$

Octave, 25 22 20 bytes

2 bytes removed thanks to a suggestion by Sanchises

@max_recursion_depth

Anonymous function that outputs the value.

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ You don't need the (), as max_recursion_depth is also a function. \$\endgroup\$
    – Sanchises
    Sep 2 '17 at 14:23
  • \$\begingroup\$ @Sanchises Thanks! You are right: even if the doc says it's a variable, it's actually a function \$\endgroup\$
    – Luis Mendo
    Sep 2 '17 at 15:12
  • \$\begingroup\$ Your edit has turned this in a duplicate of the other Octave answer, hence my retained @ to keep it distinct (defining a function rather than REPL'ing the result). \$\endgroup\$
    – Sanchises
    Sep 2 '17 at 16:05
  • \$\begingroup\$ @Sanchises Actually I just changed that, although for a different reason (the code should actually define a function) \$\endgroup\$
    – Luis Mendo
    Sep 2 '17 at 16:07
  • \$\begingroup\$ Yeah the other answer is more like a program; I'm not sure if that should actually require disp (I would have included it, but that's my personal opinion on Octave REPL, and I am not sure of any meta consensus on that) \$\endgroup\$
    – Sanchises
    Sep 2 '17 at 16:21
3
\$\begingroup\$

zsh, 24 bytes

f(){f $[++i];f};set -x;f

Try it online! (See under debug)

Or 12 bytes if hardcoded values are allowed (From GammaFunction):

<<<$FUNCNEST

bash, 24 bytes

f(){ f $[++i];};set -x;f

Try it online! (See under debug)

ksh93, 27 bytes

f(){ f $(($1+1));};set -x;f

Try it online! (See under debug)

dash, 27 bytes

f(){ f $(($1+1));};set -x;f

Try it online! (Exceeds tio debug output, run it in your own shell)

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Should i=0 and the echo not be included in your byte count? \$\endgroup\$
    – Shaggy
    Sep 1 '17 at 7:28
  • \$\begingroup\$ @Shaggy: Perhaps, I have changed it to a more self-contained solution \$\endgroup\$
    – Thor
    Sep 1 '17 at 10:04
  • 1
    \$\begingroup\$ Zsh: <<<$FUNCNEST for 12 bytes \$\endgroup\$ Mar 1 '20 at 20:19
1
\$\begingroup\$

Lua, 52 bytes

f=load"b,e=pcall(f,(...or 3)+1)return b and e or..."

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ @Shaggy in this case yes, because I use the name f. If this wasn't recursive I could get away with not having it \$\endgroup\$
    – ATaco
    Sep 1 '17 at 12:40
  • \$\begingroup\$ Ah, I didn't spot the f in pcall. \$\endgroup\$
    – Shaggy
    Sep 1 '17 at 12:42
  • \$\begingroup\$ why does your program stops at 200? here you can see that in that simple function it goes beyond 200. if you remove the -- you can confirm that it is still a recursive call with no optimizations \$\endgroup\$ Sep 1 '17 at 14:56
1
\$\begingroup\$

q/kdb+, 16 bytes

Solution:

{@[.z.s;x+1;x]}0

Example:

/ solution
q){@[.z.s;x+1;x]}0
2000

/ without apply (try/catch)
q){.z.s x+1}0
'stack
@
{.z.s x+1}
2001

Explanation:

Try to recurse, increase x by one each time, if error, return x.

{@[.z.s;x+1;x]}0 / the solution
{             }0 / call lambda function with 0
 @[    ;   ; ]   / @[function;argument;catch]
   .z.s          / call self (ie recurse)
        x+1      / increment x
            x    / return x if function returns error
\$\endgroup\$
1
\$\begingroup\$

Excel-VBA, 26 Bytes

?Application.MaxIterations

Not recursion depth per-se, this actually outputs the maximum number of iterations for a cell in an Excel worksheet. Given that the output pertains to a language other than the language in which this is written, perhaps this is more appropriate:

Excel + Excel-Vba, 3 + 38 = 41 Bytes

Function f:f=Application.MaxIterations

As that can be called from a cell with

=f(

For VBA with no built in:

Excel-VBA, 53 44 40 bytes

-9 as variable no longer needs to be initialised or printed

-4 as code execution no longer has to be ended to avoid multiple prints

Sub s:[A1]=[A1]+1:On Error Resume Next:s

Call with s in the immediate window, outputs to cell A1 of the worksheet

(warning takes a while to run now, add Application.ScreenUpdating = False first)

\$\endgroup\$
1
\$\begingroup\$

Lua, 45 37 bytes

x=2
f=load"x=x+1;f()"pcall(f)print(x)

Try it online!

I don't know which value to initialize x with as I don't know the number of intermediary calls there are...

\$\endgroup\$
1
\$\begingroup\$

Clojure, 72 55 48 bytes

-23 bytes by getting rid of the atom

-7 bytes thanks to @madstap. Switched to using fn over def and #(), and pr over println.

((fn f[i](try(f(inc i))(catch Error e(pr i))))0)

Wrote and tested on my phone. The Clojure REPL app gave me a depth of 13087.

Basic solution. Recurse until a SO is thrown, incrementing a counter each recurse. When it's thrown, the value of the counter is printed.

\$\endgroup\$
2
  • \$\begingroup\$ You can save 5 bytes by using pr instead of println. Also -2 bytes by making the fn like this: ((fn f[x](,,,))0) instead of (def f #(,,,))(f 0). \$\endgroup\$
    – madstap
    Sep 2 '17 at 4:29
  • \$\begingroup\$ @madstap Thanks. I'll make the changes in a bit. \$\endgroup\$ Sep 2 '17 at 10:24
1
\$\begingroup\$

VBA, any type, 41 39 bytes

Function A:On Error Resume Next:A=A()+1

Call using ?A() in the Immediate window, or as worksheet function.

Note: Returns 4613 in Excel-VBA, while the answer by @Greedo returns 3666 on my system (highest should be the max). Apparently also varies between Office programs (Access-VBA returns 4622, Word-VBA 4615)

Edit: Guess VBA auto-adds parantheses, so removed them.

\$\endgroup\$
0
\$\begingroup\$

Pyth - 9 bytes

L.xyhbbyZ

If I can run it like the J answer above, this is 7 bytes because you can take out the last yZ.

Try it online here.

\$\endgroup\$
2
  • 5
    \$\begingroup\$ This doesn't work for me. Offline, I get a segmentation fault. Online, I get no output at all. You can't catch a segfault. \$\endgroup\$
    – isaacg
    Sep 1 '17 at 5:08
  • \$\begingroup\$ @isaacg wait this is really weird. Online, it rarely gives 764, but you're right most of the time it gives no output. \$\endgroup\$
    – Maltysen
    Sep 1 '17 at 19:26
0
\$\begingroup\$

Forth, 48 bytes

Loops until it hits the limit.

: m 1+ recurse ;
: f 0 ['] m catch drop ; f .

Try it online

\$\endgroup\$
0
\$\begingroup\$

Tcl, 18 bytes

puts [interp r {}]

Try it online!

recursionlimit can be abbreviated to r

Tcl, 31 bytes

puts [interp recursionlimit {}]

Try it online!

\$\endgroup\$
0
0
\$\begingroup\$

Tcl, 49 bytes

proc R {i\ 1} {if [catch {R [incr i]}] {puts $i}}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Ruby, 39 bytes

END{p$.}
$stderr=$<
f=->{$.+=1;f[]}
f[]

Suppressing the error message is a little shorter than rescuing it, since by default rescue doesn't catch SystemStackError.

There's a cheesier answer if I can output in unary, representing n with n consecutive newline characters:

Ruby, 35 bytes

$stderr=$<
f=->{puts;$.+=1;f[]}
f[]
\$\endgroup\$
0
\$\begingroup\$

Jelly, 18 bytes

:( *

“¡żuẋ×HẒpƙ7"8!ƭ»ŒV

Try it online!

How?

* Since Jelly as far as I am aware:
(1) sets the Python recursion limit prior to setting up much of its own interpreter and parsing the code to be run; and
(2) has no way of catching Python errors
I'm not sure if there is a way to either reliably evaluate the recursion limit or to print it out as it is discovered other than to actually ask Python what the value was set to (I'd love to see if it can be done though!) so that's what the code here does:

“¡żuẋ×HẒpƙ7"8!ƭ»ŒV - Link: no arguments
“¡żuẋ×HẒpƙ7"8!ƭ»   - compression of "sys."+"get"+"recursion"+"limit"+"()"
                ŒV - evaluate as Python code
\$\endgroup\$