7 ms·
"There was just one catch: You can't do recursion." You could do tail recursion, because only the return address of the first call would be needed to be stored
by weinzierl 3y ago
"There was just one catch: You can't do recursion."
You could do tail recursion, because only the return address of the first call would be needed to be stored. `branch_with_link` would be used for the initial call, but the recursive calls would have to be regular branches.
- Joel_Mckay 3y agoMost recursion is about as bad as goto coding methodologies. Personally, I think it should be avoided in modern compiled languages too. Haskell is fun to play around on, but it is horrific to consider using in a stable production environment. =)
- autoexecbat 3y agoOutside of a university course, if I see recursion in a non-FP language I consider it a code-smell
- mikepurvis 3y agoThe only time I ever do it is for tree walking, and then it's always a private internal function, so like: def process_that_tree(my_tree): def _handle(node): # do the things for child in node.children: _handle(child) _handle(my_tree.root) The processing can even be brought outside sometimes, or the walker can just become a generator, yielding nodes out to a regular loop doing the actual work. Either way, the recursive part is kept very minimal and easy to reason about. Obviously for the filesystem these kinds of abstractions exist already in shutil/pathlib/glob, but it still can have a place for dealing with other kinds of hierarchies, like a package dependency tree or the like.
- II2II 3y agoWhile I am not a fan of recursion, the call stack that enables it sounds infinitely better than statically allocating space for parameters and return values. Besides, it makes some algorithms clearer. That is certainly useful in learning environments, including early academic research.
- Joel_Mckay 3y agoDepends on the CPU, in some architectures the stack pointers had low finite capacity before overflowing.
- munificent 3y agoThis opinion is totally wild to me. Do you never work with tree data structures? I can't think of a non-trivial program I've written in the past two decades that didn't have some recursive tree traversal in it.
- Arnavion 3y agoTree traversal uses stacks / queues unless you're dealing with a small tree such that you're sure recursion won't blow your stack, or your algorithm can work with tail calls and your language guarantees TCO.
- mannyv 3y agoRecursion in production code is bad news, because you can't control the depth of your call tree. At some point you will crash because the runtime won't be able to allocate any more stack. And you can't preflight it because if you could preflight it you wouldn't be doing recursion. Recursion is a nice toy, but in real life it's a ticking time bomb.
- josephg 3y agoIf you're using some sort of balanced tree (red-black, AVL or a b-tree of some sort), the depth of the tree is guaranteed to be log(n) where n is the number of items. If you recursively descend down the tree, the number of stack frames involved will never exceed the height of the tree. If you have a binary tree with 1 billion elements, the depth will be 20. In a b-tree with a reasonable node width (eg 16), assuming 50% occupancy the depth will be about 8. This is, in practice, totally fine. You won't exhaust your stack traversing a balanced tree.
- nerpderp82 3y agoRecursion is like an inductive proof, you can show it is correct and it normally fits on half of a small screen.
- Joel_Mckay 3y agoThere is an argument that all recursive proofs can be made iterative due to isomorphism. You are not lazy enough to be a good programmer yet. ;-)
- nerpderp82 3y agoYeah, but that is error prone and more complex. A compiler can make those same transformations. I'd argue that the properly lazy programmer is the one using recursion. To get even lazier, one should move into relational algebra.
- Joel_Mckay 3y agoMeh, or just choose a documented data structure that supports your problem scope. If it takes longer than 1 coffee, than someone is usually approaching things the wrong way... Have to think "minimum effort" here... ;-)
- nerpderp82 3y agoI have seen 150 lines of SQL replaced with 12k lines of Java.
- Joel_Mckay 3y agoOnly 12k lines? That is efficient for most Java programmers. =)
- nerpderp82 3y agoThank you! :)
- EdwardCoffin 3y agoI'd recommend you read Guy Steele's blog post Why Object-Oriented Languages Need Tail Calls [1] and perhaps the essay by William Cook [2] and the discussion over on Lambda the Ultimate [3] [1] https://web.archive.org/web/20091206042608/http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion https://web.archive.org/web/20091206042608/http://projectfor... [2] https://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf https://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf [3] http://lambda-the-ultimate.org/node/3702 http://lambda-the-ultimate.org/node/3702
- Joel_Mckay 3y agoSure, or just add a polymorphic functor to walk a tree autonomously. There are shorter ways to admit you already sold your soul. lol =)
- tome 3y agoIt's interesting because I love using Haskell in a stable production environment. In fact I'd hate to use anything else! On the other hand, I almost never use naked recursion in Haskell. It typically do recursion indirectly through more familiar combinators such as for loops.
- Joel_Mckay 3y agoI like Haskell in many ways as it shifts ones perspectives, but it is just way too easy to leave unpredictable behaviors unconstrained. =)
- CyberDildonics 3y agoI agree. People love making things clever instead of making things done. Recursion for iteration is just more complicated iteration. I've never seen a good argument for it in modern programming, it just ends up being the classic backwards rationalization of something people want to believe. Recursion for traversing a tree is just using the call stack as a stack data structure. Any balanced tree is never going to exceed 64 levels deep (really 48 on a 48 bit memory addressing cpu) and that could easily be put in a static array that gets used as a stack without recursing. This is easier to limit and debug.
- samatman 3y agoThe same argument suggests that a recursive stack traversal will never consume more than 64 stack frames, so consuming stack frames is no reason not to use a recursive function. It's just as easy to limit recursion depth, if you need to, just pass along a counter and check it. I haven't found that hand-rolling a second stack, instead of using the program stack, is easier to debug, the opposite if anything, but your mileage may vary on that one.
- CyberDildonics 3y agoso consuming stack frames is no reason not to use a recursive function. Saving stack memory isn't the point (even though a static array definitely does, because instead of multiple pointers and variables on the stack it only would have to store the node index of a tree). The point is that you can see the whole stack and all the data that you're using at one time in a debugger instead of trying switch through call stacks to find data.
- sham1 3y agoWell, it's still recursion whether you're using the call stack or are using an explicit stack structure. You're still breaking the problem down into smaller subproblems inductively. I feel that people focus on the wrong things when talking about recursion, focusing on the aspect of having a function calling itself instead of the idea of having the problem solved by way of breaking it down into smaller problems.
- twoodfin 3y agoThis limitation doesn’t just proscribe traditional recursive algorithms: Any reentrancy is impossible. Your threads, co-routines, interrupt handlers, error handlers, all have to be careful not to stomp on someone else’s use of the same function, even if they’re not directly using a function recursively.
- wglb 3y agoYes, but you do need to handle local storage.