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.
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.
> 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. :)
'Doing a binary tree'? You mean visiting every node?
define walk-tree (tree fn &optional remaining-branches)
match tree
(Leaf l) ->
funcall fn l
if remaining-branches
walk-tree (first remaining-branches) fn (rest remaining-branches)
(Tree t r l) ->
funcall fn t
walk-tree r fn (push l remaining-branches)
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?
This page does not identify an algorithm that can be implemented in fixed space but is hard or impossible to do with tail recursion. No such algorithm exists. It is unclear which of the dozens of beautiful algorithms it presents you mistakenly believed to be one.
Traversing a mutable binary tree can be done in fixed space but is not easier to do with generalized forms of recursion than with tail recursion or imperative iteration.
For saying that you cannot write algorithms to deal with binary trees using tail recursion. Saying code is used to access a binary tree is a trivial statement with no value to it. Nobody is going to even bother responding to that because of how obvious it is.
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.
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.
