5 ms·

I live by "don't recurse, iterate". Don't get me wrong, recursion seems really clever, if you live in a universe with an infinite stack.

philzook 2y ago
I like what I find clearest (a moving target for all sorts of reasons). I typically find recursion clearest for things dealing with terms/ASTs. My coding style usually leans towards comprehensions or fold/map etc rather than loops. That's why I find the loop being clearer for this algorithm surprising.
- tines 2y ago
  Same here, the answer is easy for me: recursive algorithms are for recursive data structures.
- CodeWriter23 2y ago
  Calling this out. A loop calling a function in terms of style is roughly the same as a function calling itself.
norir 2y ago
I personally take the opposite approach. Tail recursion fixes the stack problem and just about any problem that can be solved recursively can be reworked to be made tail recursive. Using tail recursion instead of loops forces you to name the procedure, which is helpful documentation. Also, unlike a loop, you have to explicitly call back into it. For me, the edge cases are usually clearer with tail recursion and I find it harder to write infinite loops using tail recursion. Regular non tail recursion can be fine in many cases so long as the recursion depth is limited. I have tested code that made at least 50000 recursive calls before blowing the stack. In many cases, you can just assume that won't happen or you can rewrite the function in a tail recursive way by adding additional parameters to the function with a slight loss of elegance to the code.
- jancsika 2y ago
  > Tail recursion fixes the stack problem and just about any problem that can be solved recursively can be reworked to be made tail recursive. To cover all cases, I feel like there needs to be a cross-platform drop-in library to properly blow the stack in languages which feature tail call recursion. :)
- evujumenuk 2y ago
  In my younger years, I used to employ the Y combinator as a way to avoid naming recursive functions because I didn't want to necessarily dignify single-use code by abstracting it into a named function that I'd never call anywhere else. Instead of calling itself in the non-base case, the anonymous lambda simply calls a first-class function passed into it, with the necessary plumbing abstracted into the generic combinator. Fixed-point combinators can be made to work with tail recursion, so I don't think tail recursion forces anyone to name anything. Certainly, how easy it is to go with this particular approach depends a lot on the semantics of your chosen (or imposed) programming language.
readthenotes1 2y ago
"recursion seems really clever, if you live in a universe with an infinite stack." Recursion seems really clever if you live in a universe with clever coworkers maintaining your code a few years from now.
- CodeWriter23 2y ago
  Glad someone else gets it.
Someone 2y ago
As others indicated, tail recursion exists. There are also languages where the standard guarantees code will use tail recursion in certain cases. An example is scheme (https://people.csail.mit.edu/jaffer/r5rs/Proper-tail-recursion.html https://people.csail.mit.edu/jaffer/r5rs/Proper-tail-recursi...) There also are languages where you can write recursive functions in a way that makes the compiler err out of it cannot make the calls in a tail-recursive way. An example is scala (https://www.scala-lang.org/api/2.12.1/scala/annotation/tailrec.html https://www.scala-lang.org/api/2.12.1/scala/annotation/tailr...) That removes the possibility that a programmer mistakenly believes the compiler will use tail recursion.
- CodeWriter23 2y ago
  Try doing a binary tree with tail recursion.
  - deleted 2y ago
    [deleted]
  - tylerhou 2y ago
    It’s not as difficult as you might think; take the recursive code and turn it into CPS style.
  - Someone 2y ago
    A binary tree is a data structure, tail recursion is used in code ⇒ what algorithm are you thinking of that can be implemented in fixed space but is hard or impossible to do with tail recursion?
    - CodeWriter23 2y ago
      are you kidding me right now? How do you think the data structure is accessed? Hint: code You youngun's have hidden behind APIs for so long you don't even know how things work.
    - CodeWriter23 2y ago
      I’m not going to apologize for being harsh. But I will link a resource to help you understand. http://cslibrary.stanford.edu/110/BinaryTrees.html http://cslibrary.stanford.edu/110/BinaryTrees.html
lioeters 2y ago
It depends on the language and problem space, but I agree in general. Rewriting a recursive algorithm to be iterative is better done at an early stage of a program, or start iteration to begin with, because it gets increasingly difficult as the program grows in size and complexity. It's too late to think about if/when the stack blows, so better think about it before/as you write the logic.
jasdfywu 2y ago
iterative recursion does not use stack frames in languages that support TCO.

philzook 2y ago

I like what I find clearest (a moving target for all sorts of reasons). I typically find recursion clearest for things dealing with terms/ASTs. My coding style usually leans towards comprehensions or fold/map etc rather than loops. That's why I find the loop being clearer for this algorithm surprising.

tines 2y ago
Same here, the answer is easy for me: recursive algorithms are for recursive data structures.
CodeWriter23 2y ago
Calling this out. A loop calling a function in terms of style is roughly the same as a function calling itself.

norir 2y ago

I personally take the opposite approach. Tail recursion fixes the stack problem and just about any problem that can be solved recursively can be reworked to be made tail recursive. Using tail recursion instead of loops forces you to name the procedure, which is helpful documentation. Also, unlike a loop, you have to explicitly call back into it. For me, the edge cases are usually clearer with tail recursion and I find it harder to write infinite loops using tail recursion. Regular non tail recursion can be fine in many cases so long as the recursion depth is limited. I have tested code that made at least 50000 recursive calls before blowing the stack. In many cases, you can just assume that won't happen or you can rewrite the function in a tail recursive way by adding additional parameters to the function with a slight loss of elegance to the code.

jancsika 2y ago
> Tail recursion fixes the stack problem and just about any problem that can be solved recursively can be reworked to be made tail recursive. To cover all cases, I feel like there needs to be a cross-platform drop-in library to properly blow the stack in languages which feature tail call recursion. :)
evujumenuk 2y ago
In my younger years, I used to employ the Y combinator as a way to avoid naming recursive functions because I didn't want to necessarily dignify single-use code by abstracting it into a named function that I'd never call anywhere else. Instead of calling itself in the non-base case, the anonymous lambda simply calls a first-class function passed into it, with the necessary plumbing abstracted into the generic combinator. Fixed-point combinators can be made to work with tail recursion, so I don't think tail recursion forces anyone to name anything. Certainly, how easy it is to go with this particular approach depends a lot on the semantics of your chosen (or imposed) programming language.

readthenotes1 2y ago

"recursion seems really clever, if you live in a universe with an infinite stack." Recursion seems really clever if you live in a universe with clever coworkers maintaining your code a few years from now.

CodeWriter23 2y ago
Glad someone else gets it.

Someone 2y ago

As others indicated, tail recursion exists. There are also languages where the standard guarantees code will use tail recursion in certain cases. An example is scheme (https://people.csail.mit.edu/jaffer/r5rs/Proper-tail-recursion.html https://people.csail.mit.edu/jaffer/r5rs/Proper-tail-recursi...) There also are languages where you can write recursive functions in a way that makes the compiler err out of it cannot make the calls in a tail-recursive way. An example is scala (https://www.scala-lang.org/api/2.12.1/scala/annotation/tailrec.html https://www.scala-lang.org/api/2.12.1/scala/annotation/tailr...) That removes the possibility that a programmer mistakenly believes the compiler will use tail recursion.

CodeWriter23 2y ago
Try doing a binary tree with tail recursion.
- deleted 2y ago
  [deleted]
- tylerhou 2y ago
  It’s not as difficult as you might think; take the recursive code and turn it into CPS style.
- Someone 2y ago
  A binary tree is a data structure, tail recursion is used in code ⇒ what algorithm are you thinking of that can be implemented in fixed space but is hard or impossible to do with tail recursion?
  - CodeWriter23 2y ago
    are you kidding me right now? How do you think the data structure is accessed? Hint: code You youngun's have hidden behind APIs for so long you don't even know how things work.
  - CodeWriter23 2y ago
    I’m not going to apologize for being harsh. But I will link a resource to help you understand. http://cslibrary.stanford.edu/110/BinaryTrees.html http://cslibrary.stanford.edu/110/BinaryTrees.html

lioeters 2y ago

It depends on the language and problem space, but I agree in general. Rewriting a recursive algorithm to be iterative is better done at an early stage of a program, or start iteration to begin with, because it gets increasingly difficult as the program grows in size and complexity. It's too late to think about if/when the stack blows, so better think about it before/as you write the logic.

jasdfywu 2y ago

iterative recursion does not use stack frames in languages that support TCO.