Check if function is declared recursive

Question

Is it possible to check if a function was declared as recursive, i.e. with let rec?

I have a memoize function, but it doesn't work with arbitrary recursive functions. I would like to give an error if the user calls it with such a function. (Feel free to tell me if this is a bad way to deal with errors in F#)

What is an "arbitrary recursive function"? Can you give some code examples of what you're asking about? — CoderDennis, Aug 31 '15 at 19:46

Petr · Accepted Answer · 2015-08-31T19:19:48.067

5

F# code is compiled to .NET Common Intermediate Language. F# rec keyword is just a hint to F# compiler that makes identifier that is being defined available in the scope of the function. So I believe that there is no way to find out at runtime that the function is declared as recursive.

However you could use System.Diagnostic.StackTrace class (https://msdn.microsoft.com/en-us/library/system.diagnostics.stacktrace.aspx) to get and analyze stack frames at runtime. But accessing stack information have significant performance impact (I'm assuming that your memoization function is for speeding up program performance). Also stack information could be different in Debug and Release versions of your program as the compiler can make optimizations.

edited Aug 31 '15 at 19:19

answered Aug 31 '15 at 19:09

Petr

4,280
1
19
15

Wouldn't the stack trace approach fail miserably for tail-recursive functions (and what's worse - fail only in Release mode by default)? Unless tail recursion leaves enough information on the stack that you can tell you're doing recursion? – scrwtp Aug 31 '15 at 22:10
Probably yes, and also as I said stack trace approach will impact performance significantly – Petr Aug 31 '15 at 22:44
Thanks for the explanation. It is nice to know that ´rec´ really is just a compiler hint (although the info could have been stored someplace and found using reflection). The StackTrace solution is interesting. I assume due to the non-circular nature of F#, a function must be recursive if it appears twice in the call stack. And no, I wouldn't really use that to optimize - I'm mostly just interested and curious, and trying to help myself learn and understand the language better :) – MariusUt Sep 02 '15 at 09:03

score 2 · Answer 2 · edited May 23 '17 at 12:22

I don't think it can be done in a sensible and comprehensive manner.

You might want to reevaluate your problem though. I assume your function "doesn't work" with recursive functions, because it only memoizes the first call, and all the recursive calls go to the non-memoized function? Depending on your scenario, it may not be a bad thing.

Memoization trades off memory for speed. In a large system, you might not want to pay the cost of memoizing intermediate results if you only care about the final one. All those dictionaries add up over time.

If you however particularly care about memoizing a recursive function, you can explicitly structure it in a way that would lend itself to memoization. See linked threads.

So my answer would be that a memoize function shouldn't be concerned about recursion at all. If the user wants to memoize a recursive function, it falls to him to understand the trade-offs involved, and structure the function in a way that would allow intermediate calls to be memoized if that's what he requires.

Check if function is declared recursive

2 Answers2