Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
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!
def f(x=2):
try:f(x+1)
except:print(x)
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.
f=_=>do{try{-~f()}catch(e){}}
Try it here, or use the Snippet below to test it with eval instead of do.
console.log((f=_=>eval(`try{-~f()}catch(e){}`))())It's not really worth posting this as a separate solution as it's, essentially, identical.
Ox`try\{-~rp()}¯t®(e)\{}
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){}`)
f=_=>eval('try{-~f()}catch(e){}')
\$\endgroup\$
#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)
1+$: ::]
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.
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.
(1+$: ::]) 0
\$\endgroup\$
import sys
sys.getrecursionlimit
Saved 9 bytes thanks to @FryAmTheEggman!
from sys import*
getrecursionlimit
__import__('sys').getrecursionlimit
The last 2 are thanks to @totallyhuman
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:
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
int c(){try{return-~c();}catch(Error e){return 1;}}
\$\endgroup\$
int c(){int n=1;try{n=-~c();}finally{return n;}} saves 3 bytes but gives me a different answer?
\$\endgroup\$
int c(){int n=1;try{n+=c();}finally{return n;}}
\$\endgroup\$
int d;int c(){try{c();}finally{return++d;}}
\$\endgroup\$
-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)));}
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.
max_recursion_depth
Usage:
octave:1> max_recursion_depth
ans = 256
-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.
ressions due to partial matching with $.
\$\endgroup\$
Sep 1, 2017 at 5:36
2 bytes removed thanks to a suggestion by Sanchises
@max_recursion_depth
Anonymous function that outputs the value.
(), as max_recursion_depth is also a function.
\$\endgroup\$
Sep 2, 2017 at 14:23
@ to keep it distinct (defining a function rather than REPL'ing the result).
\$\endgroup\$
Sep 2, 2017 at 16:05
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\$
Sep 2, 2017 at 16:21
f(){f $[++i];f};set -x;f
Try it online! (See under debug)
Or 12 bytes if hardcoded values are allowed (From GammaFunction):
<<<$FUNCNEST
f(){ f $[++i];};set -x;f
Try it online! (See under debug)
f(){ f $(($1+1));};set -x;f
Try it online! (See under debug)
f(){ f $(($1+1));};set -x;f
Try it online! (Exceeds tio debug output, run it in your own shell)
-- you can confirm that it is still a recursive call with no optimizations
\$\endgroup\$
Sep 1, 2017 at 14:56
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
?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:
Function f:f=Application.MaxIterations
As that can be called from a cell with
=f(
For VBA with no built in:
-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)
x=2
f=load"x=x+1;f()"pcall(f)print(x)
I don't know which value to initialize x with as I don't know the number of intermediary calls there are...
-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.
pr instead of println. Also -2 bytes by making the fn like this: ((fn f[x](,,,))0) instead of (def f #(,,,))(f 0).
\$\endgroup\$
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.
L.xyhbbyZ
If I can run it like the J answer above, this is 7 bytes because you can take out the last yZ.
764, but you're right most of the time it gives no output.
\$\endgroup\$
Loops until it hits the limit.
: m 1+ recurse ;
: f 0 ['] m catch drop ; f .
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:
$stderr=$<
f=->{puts;$.+=1;f[]}
f[]
:( *
“¡żuẋ×HẒpƙ7"8!ƭ»ŒV
* 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
