3 ms·
I thought that self recursion was fine so long as the calls were provably "smaller problems" than the function calling them, something like "bounded recursion".
by SilasX 9y ago
I thought that self recursion was fine so long as the calls were provably "smaller problems" than the function calling them, something like "bounded recursion".
- nine_k 9y agoIf you can prove that the recursion is bounded, great! But sometimes it is hard, and I'm afraid it's equivalent to the halting problem in general case. Without recursion, though, finding the maximal depth of the call graph is definitely solvable, and likely not even very hard.
- SilasX 9y agoReally? I thought the problems were equivalent, of proving that e.g. a loop vs its recursive equivalent were bounded. Side note: an interesting case is the Stable Marriage Problem. It's easy to write the O(n) algorithm and prove its bound, but it's hard to translate into a bounded recursive algorithm that does the same thing. (At least as far as I understand -- I searched it on Stack Overflow and that's what it said, and I've tried the problem itself. A Coq fanatic insisted that "if you can prove the run time is bounded it's easy to write the bounded recursive equivalent" but somehow that never translated into an actual insight on how to do it.)
- UncleMeat 9y agoProving that a loop is bounded is also undecidable.
- Thiez 9y agoOnly in the general case. In many/most loops that humans would find useful in practice you can prove termination.
- nine_k 9y agoIn general case, yes, of course. There are still cases where you can prove that a recursion is bounded (I suppose something like dependent types could help here). There are definitely cases where you can prove that a loop is bounded, because the semantics of the language requires them to: a loop with a counter (not otherwise mutated), iteration over a known finite structure, etc. Well, both C++ and Haskell allow you to use compiler features that are undecidable in general case, but usually work well in practical cases. Also, if e.g. your recursion / loop analysis is taking too long, you can just stop the analyzer. If the code can't be reasonably proved right, it should be considered wrong (with a chance of a false negative).
- qznc 9y agoYou might be thinking of Total Functional Programming [0] "a programming paradigm that restricts the range of programs to those that are provably terminating." [0] https://en.wikipedia.org/wiki/Total_functional_programming https://en.wikipedia.org/wiki/Total_functional_programming