[13415]

Tail call optimization is more or less unimportant, because you can express any recursion with iteration and most of the time the explicitly iterative version is even safer and better. TCO only adds zero-cost for recursions based on tail calls, that's nice to have but recursion is a bit of a hobby-horse of CS professors anyway. It only makes sense in languages that have their own stack, i.e., have no hard stack limit except for your main memory, otherwise you will run out of stack space soon. Iterative versions of functions are often easier to understand, too.

[nybble41]

> TCO only adds zero-cost for recursions based on tail calls

TCO isn't about recursion; it applies to any function call in tail position. Some toolchains only manage to avoid over-allocating stack frames for self-recursive tail calls, but that isn't full TCO, and it doesn't help for other interesting case like mutual recursion, state machines, or continuation-passing style. Compilers which compromise on full support for TCO emit programs with built-in memory leaks; they fail to free data which is no longer needed, and thus unnecessarily exhaust their stack allocation.

Programs which use built-in iterative constructs are still recursive; all that "recursion" means is that the control flow folds back on itself. A traditional "while" loop looks like: (1) stop if a condition is false; (2) otherwise do something; (3) do it again. The "it" in (3) is a recursive reference to the loop.

Now, unstructured explicit recursion is barely better than unstructured "goto", so I'm not advocating that everyone start using tail calls in place of loops. However, bare loops are in much the same position with respect to higher-order primitives such as non-strict folds—and those higher-order primitives are much easier to implement in environments which properly support TCO. Languages where TCO is not customary tend to suffer from a proliferation of built-in constructs—iteration, generators, list comprehensions, coroutines, and the like are all implemented as language features requiring custom code generation, where another language where TCO is customary might relegate such primitives to a library.

[Jtsummers]

Recursion is great, IMHO, as a non-professor type. It allows for much clearer expressions of intent for my methods and functions than the iterative version often achieves.

There are some recursive structures that are just much more natural than their iterative counterparts. Parsing (as lysium suggests in the sibling post), for example.

But also things like graph and tree traversals, and many search algorithms related to those same structures. If you attempt a tree traversal iteratively, you have to maintain the return stack manually, rather than permitting the language to do it for you (assuming a full traversal and not a search, a search could be done iteratively without much trouble).

[13415]

I'd say the opposite. Mutually recursive functions are notoriously hard to get right and debug, and many languages have stack limits. Often it's better to maintain the stack manually.

[Jtsummers]

That has not been my experience, but I know many people who agree with you. IME, the difference has been that I came into CS with a more mathematical (formal) approach to programming, and they tended to come at it with a more mechanistic approach (especially when I hear it from non-CS developers, often EEs).

[rydel]

It depends. As we know, FP is all about not having side effects. Having “for” loop requires to mutate the pointer of given iteration.

[pjmlp]

As replied on another thread, you just killed a couple of FP languages with that definition.

[nybble41]

Those are not FP languages. They are, at best, "functional-first" multi-paradigm languages. (Common Lisp and Scheme are in this category.) Unfortunately, FP is more about what is excluded (side effects) than what is included (closures, continuations, sum types, etc.), so mixing FP with any amount of imperative/procedural code tends to result in an awkward and less efficient form of imperative programming without the primary benefit of FP (referential transparency).

The "function" in "functional programming" refers to mathematical functions, which are fixed mappings from inputs to results with no side effects. If your "functions" can have side-effects then they're not functions, they're procedures. Programs composed of effectful procedures are imperative, not functional.

[lysium]

Did you consider mutual recursive functions in your answer? For example implementations of parsers?

[rydel]

Another thing about recursion is that it is really powerful for operation on tree like data structures/objects