5 ms·
> Recursion over Looping Part of what makes Clojure a great programming language is that you don't have to believe this if you don't want to. Nobody has yet co
by roenxi 4y ago
> Recursion over Looping
Part of what makes Clojure a great programming language is that you don't have to believe this if you don't want to. Nobody has yet convinced me that recursion has any sustained advantage over looping.
Using a loop is generally bad practice if a more specialised operation is available (don't loop if something is a simple map or reduce for example). But if the situation justifies a recursion then it usually justifies a loop unless the recursion is particularly neat. Recursion has the same problem as looping - it doesn't tell anyone anything about what the code is really doing. If I see map then I have implicit and explicit expectations about what is about to happen.
I enjoyed the article though.
- nerdponx 4y agoI think the difference between recursion and looping is that the former requires you to be very explicit about the state you intend to modify and persist between iterations, while it's generally somewhat of a free-for-all in imperative loops.
- slifin 4y agoThe most common looping construct I see in clojure is the for statement Which isn't quite the free for all it is in traditional languages You have to be very conscious and coding against the grain to use it to bang on values in place
- nerdponx 4y agoThis is a general design principle that I appreciate about the Lisp family of languages in general. You can write highly imperative code that mutates things in-place, but it's a little harder to do and it's something you do only when you really need to do it. Whereas the default idioms are functional, and functional design is the path of least resistance. Perl is morally the opposite of functional programming in many ways, but I actually think this design is a great embodiment of the "make easy things easy, make hard things possible" ethos of Larry Wall.
- js8 4y agoI mostly agree, and proponents of FP shouldn't stress the recursion too much. When I program in Haskell, I rarely use recursion myself. Most loops are just maps and folds. Need to build another structure from existing structure? Foldl'. Once I understood that the value being folded can be arbitrarily complex, FP became simpler (but terser) than iterative programming for me.
- janetacarr 4y agoAgreed, I rarely reach for recursion myself when developing. Most of my transformations are map, filter, and reduce. Although from time to time, I will combine them with recursion when necessary. I find recurring from a reducing function to be great for traversing or searching trees or other recursive data structures. Usually these are accompanied by a ton of comments for the next developer. :)
- ballenf 4y agoI don't think of map operations as loops. Instead as parallel operations on elements of a list works as a better mental model for me. When learning them coming from an imperative background, it's inevitable to start with that idea, but somehow feels like a limiting model.
- PartiallyTyped 4y agoMaybe it's my background but recursion feels more natural, either you are at the base, or at a point with N-1 items below. This gives you two different invariants that you can use to simplify the code. Small example, though not exactly comparable to looping. I needed to create a human readable qualified path appended by a hash (to avoid conflicts). This qualified path was needed ahead of the construction of an object, and the logical name must have been used in both the hash and qualified path as it was global (Yes, it was an S3 bucket). I wrote a function uniqueQualifiedName: Construct x Optional(logicalId) x Properties -> string. The recursive step is at the top, where the logicalId is transformed to a construct in the scope of the first argument, and the function is called again with NewConstruct x Nothing x Properties. This could easily be adjusted to work with a list of logicalIds instead. The invariant in the recursive step is that once the call returns, the construct at the end of the chain will be exactly the construct I inserted, and I can pop it safely, and the scope object will be none the wiser. The invariant in the base is simply that I don't need to worry about logicalId being anything. You can see then how easy it is to adapt this to work with a list, whereas with a loop you'd have to write it from zero, and then roll back. Too messy imho.
- roenxi 4y agoI don't understand your problem or your solution, but that seems like a lot of things going on to construct a string. But it sounds like you could just bash the logicalIds together and append the hash of the bash of the mash. Might not need loops or recursion.
- PartiallyTyped 4y agoTo just bash them together I'd have to either use the private api which is not a good thing. Alternatively I can push a list of items N steps to each object and have each one of them both adding and removing the logical names.
- chriswarbo 4y ago> Nobody has yet convinced me that recursion has any sustained advantage over looping. Looping may require trampolining or defunctionalisation, whilst recursion can be written much more directly and simply. As a very simple example (in pseudocode): even(n: uint): boolean = n match { case 0: true case n: odd(n-1) } odd(n: uint): boolean = n match { case 0: false case n: even(n-1) } Whilst these are pretty silly implementations of odd & even, I don't know of a direct analogue using loops. For more realistic examples, just look at any "main loop"; AKA "trampoline boilerplate to work-around our language's lack of tail-call elimination" ;)
- roenxi 4y agofor(range(n)): is_true = !is_true And adjust for all the off by 1 errors. You're managing the same amount of state both ways, but with the loop all the state mutation lives on one line instead of spread throughout a stack.
- chriswarbo 4y agoThat's not a "direct analogue" of my implementation, for many reasons; you've changed the semantics and engineering tradeoffs so much that we might as well write `n % 2 == 0`. The biggest problem is that, assuming we copy your snippet into a couple of function definitions, we've completely lost the encapsulation/separation-of-concerns/delegation/etc. provided by my `odd` and `even` functions; i.e. all of the "software engineering" stuff that makes source code more maintainable than disassembled binary. Your loop is more like the following, which is not what I wrote: even(n: uint): boolean = n match { case 0: true case n: !even(n-1) } odd(n: uint): boolean = n match { case 0: false case n: !odd(n-1) } The major difference is the use of iteration/tail-recursion in this implementation: - This loop collapses all of the abstraction, forcing each function to implement the entire solution. In contrast, my implementation uses divide-and-conquer: only the zero case is handled directly, and the non-zero case is delegated to a more suitable handler. - Wrapping two copies of this loop into `even` and `odd` functions will completely lose the relationships inherent in my implementation. For example, if we add instrumentation, optimisations, logging, etc. to the `even` function, that will affect my `odd` function but have no effect if we were to write independent loops. - This looping implementation has extra dependencies, specifically on `range` and `!`. The `!` function requires knowledge of boolean algebra, the `range` function requires knowledge of lists/sequences/iterators, and `range` also seems to make more sophisticated use of number theory than the `odd`/`even`/`-` required to understand and maintain my implementation. Note that I'm not claiming either of these is "better"/"worse" than the other. Simply that your loop is not representative of my example; that's specifically why I chose a mutually-recursive example, and not an iterative/tail-recursive one! (Of course, all of these are exaggerations for such a simple example; but complex, real-world codebases require such engineering practices and tradeoffs to be taken seriously for the sake of maintenance)
- janetacarr 4y agoTotally! Clojure is kind of great for this, the loop form in Clojure is really recursion as `loop` just provides a point(fn) for `recur` to return as well as a let binding. You could also just call `recur` in any fn. And, it has side-effect forms like do, doseq, dotimes, etc. I'm glad you enjoyed the read though :)
- dangwhy 4y ago> Nobody has yet convinced me that recursion has any sustained advantage over looping. most sql systems support recursive queries. I believe recursive code can be analyzed by the system and executed in a the most efficient manner. Loops have sideffects closely linking them to actual execution, which makes them blackboxes to the system.
- twic 4y agoIf you're talking about recursive common table expressions, those are called recursive, but are really iterative. The PostgreSQL documentation describes the iterative evaluation: https://www.postgresql.org/docs/current/queries-with.html#id-1.5.6.12.6.3 https://www.postgresql.org/docs/current/queries-with.html#id... Note how there is no way to remove a row from the result set once it has been added. That would not be the case with a truly recursive query, because you would be constructing a new result set at every step. As a concrete example, try to write a graph query which finds all nodes exactly three edges from some starting node. That would be trivial with true recursion, but is impossible with a recursive CTE alone.
- Herval_freire 4y ago>Nobody has yet convinced me that recursion has any sustained advantage over looping. Recursion gives you a stack by default. You don't have to explicitly think about the stack. In looping the stack must be explicit. Recursion and looping are the same thing. Recursion can be mechanically translated to a for loop and a stack, the concepts are isomorphic.
- KRAKRISMOTT 4y agoOn paper perhaps, but I have yet to see a compiler that can take any arbitrary recursive subroutine and automatically optimize it into a Tail Call Optimized (that is, transform the recursive parts into goto/jumps similar to a loop) version. Non optimized recursion is not hard to understand, the problem is any performant recursive code needs to be manually rewritten as tail recursive which adds a lot of complexity. Built a better compiler and maybe more people would be willing to embrace functional programming.
- illiarian 4y agoUnless I'm mistaken, Erlang's compiler rewrites all recursion that explicitly returns a function call into tail-call, and eliminates all the stack in between
- timmg 4y ago> all recursion that explicitly returns a function call Yeah, but that's not "all recursion".
- Herval_freire 4y agoIt doesn't make any sense to convert any arbitrary recursion into tail called optimized. If the recursion can be tail called optimized then yes the loop is the optimized performant implementation. But if the recursion fundamentally utilizes the call stack then the reverse is actually true. The recursion is now the performant implementation of a for loop. So a loop conversion optimization actually doesn't make sense here. That's partly why a compiler won't optimize this. Why? Because in recursion you utilize the call stack, in the for loop you're going to create a heap allocated stack and allocate on it repeatedly. Allocation slows down the iterations. The only advantage of the for loop in this case is that there won't be stack overflow, but overall the recursive version will actually be faster.
- thewarrior 4y agoHad GPT-4 clarify some of the syntax for me https://poe.com/s/uj80au2i4TuNWgUa1pNm https://poe.com/s/uj80au2i4TuNWgUa1pNm
- janetacarr 4y agoThat's pretty cool. Armed with the fundamentals outlined in the post, my intent was for the reader to infer how he or she can design a system in FP. I'm sorry if it wasn't clear enough in the code.
- codr7 4y agoRecursion vs iteration reminds me of ordered sets vs hash tables. Maybe partly because ordered sets are often implemented as trees, which are definitely easier to traverse recursively. I find recursion nicer to work with mentally; continuous rather than discrete, with less edge cases to consider.
- tmtvl 4y agoI used Scheme for a while so I like using recursion when loops get a bit hairy, but Guy Steele's talk on Parallel Programming* made me aware of the limitations of that way of working. Now that I've switched to Common Lisp I try to think about the algebraic properties of my functions so I can apply them using lparallel's preduce. * https://www.infoq.com/presentations/Thinking-Parallel-Programming/ https://www.infoq.com/presentations/Thinking-Parallel-Progra...
- austin-cheney 4y agoLooping, as in using a loop keyword, is synchronous. Recursion is also a loop, but can iterate asynchronously as necessary. That is the primary advantage.
- KingMob 4y agoRecursion doesn't do that by default, though. And if you have to alter your code to run recursive fns on a new thread or executor, nothing prevents you from doing something similar with a loop, either.
- austin-cheney 4y agoRecursion does do that by default respective to what the given function executes. No alteration or special convention is required. Loops that require use of syntax other than a function call are synchronous only. If it would you can find me on IRC and I would be more than happy to show you how to program.
- KingMob 4y agoI see you've gone from recursion "can iterate asynchronously" to it "does do that by default". In most languages, recursion is not asynchronous, even if it could be, which is part of the point I was making. I'm guessing English is not your first language.
- librexpr 4y agoI mostly agree, but one really nice use case for recursion is when dealing with trees. For example, writing a function parse_object() that recursively calls itself to parse child objects is way more pleasant than manually managing your own stack, especially if the tree has many kinds of objects and many branches. Unfortunately in most languages this pattern will lead to stack overflow on medium-sized inputs, so you can't often use it unless you're using a language like Racket or Erlang which can't really stack overflow.