Comment by ncmncm | Hacker News Reader

Comment by ncmncm | Hacker News Reader

Parent Full thread

Manifestly, recursion is never strictly necessary, and is furthermore almost always slower, or anyway no faster, than you could do maintaining state "by hand".

But the recursive code can be much shorter, and easier to understand, because our languages have built-in apparatus to support it. They didn't always; original FORTRAN could not do recursion, and used no stack. The stack isn't free at runtime, but it's pretty cheap, and its fatal failure mode is rarely encountered nowadays.

In my work, I have always found the iterative version cleaner and faster, but that is an artifact of the kinds of problems I (and most people) solve. Having the iterative version enables more flexibility in details, because everything is explicit. E.g., escaping at the end can be much faster, and patching around errors actually possible.

Computer Science education loves to dwell on recursion far beyond its real-world usefulness, in part because CS professors carry a fondness for the Lisp of their youth, but also because arbitrarily complex problems that benefit from recursion are cheap to invent and easy to describe. In real life, recursion in any pure form rarely goes, usefully, more than three levels deep, but we like to make data structures that do.

At ITA, they did airline trip computations that would naturally recurse on the number of stops, but no one wants more stops, and time spent on possible trips with more than two is almost always wasted.

In a sense, recursion is like object-orientedness: an elegant pattern that fits many problems, but makes a poor basis for a world view or, exclusively, a language. Lisp and Smalltalk are not sidelined because of ignorance.

Ok. A fun exercise is to write a topological sort of a graph in both iterative and recursive styles.

I've used this as an interview question at least 100 times, so I've got at least 50 hours of watching people try to program this and with extremely high probability your iterative solution will be ugly and hard to follow and the recursive one very tidy. Of course, you can screw up the recursive one, but it so straightforward it almost writes itself.

On an interview I would, of course, go straight for recursion. In production, and where performance matters, I might try both.

A more meaningful interview question would be to present a recursive topo sort and ask for the iterative rendition.

I think in this particular case I'd go for the iterative one -- it's impossible to screw up (at least in the "keep track of the indegree" variant, I don't know if that's what you're thinking)

But the point you're making stands: recursion is first and foremost a thinking tool. Code as you think it need not be the same as code as you type it.

> Manifestly, recursion is never strictly necessary, and is furthermore almost always slower, or anyway no faster, than you could do maintaining state "by hand".

Recursion is required in procedures like Ackermann's Function [1]. You can still simulate or write functions that avoid the syntactic fact that the procedure definition refers (either directly or indirectly) to itself, but you'll always be papering over the fact that it cannot be implemented with a fixed number of state variables.

[1] https://en.wikipedia.org/wiki/Ackermann_function

> Recursion is required to implement non-primitive recursive procedures

This is very untrue. While loop and a stack.

> cannot be implemented with a fixed number of state variables

Of course it can't, any function outside DSPACE(O(1)) can't. The fact that you have an implicit call stack doesn't change the space complexity.

> This is very untrue. While loop and a stack.

>> You can still simulate

> any function outside DSPACE(O(1)) can't

The space complexity of the algorithm is only incidentally related to the number of unique variables required to represent it's state.

You said it best:

> The fact that you have an implicit call stack doesn't change the space complexity

As I said, and as you admit, contradicting yourself: "You can still simulate..."

We could better say that recursion is papering over a fundamental fact that the iterative form reveals. You encounter it in the recursive case, painfully, when your stack overflows. Assuming infinite memory is the fatal flaw in most modern systems.

Ackermann's function never appears in the real world.

>You encounter it in the recursive case, painfully, when your stack overflows.

People who write high performance code don't worry, because they write the recursion properly, and tail recursion doesn't use the stack.

If your understanding of recursion leads to stack overflows then you're missing a significant tool in your toolbox.

There is no more need to overflow a stack using recursion than there is to overflow a stack or heap trying to store state when unwinding a recursive function into an iterative one.

However, the recursive solution is vastly simpler in many cases since you don't have to fiddle with state, which is mutable and error prone, and can instead use immutable concepts (in any language) to write correct code more quickly with zero penalty in execution speed or space. It makes you a more valuable employee to learn these techniques.

Have you heard of this Turing fellow? He produced a result according to which a function such as Ackermann can be calculated with a read-write head moving over an unlimited tape. No recursion there.

I believe you can fairly easily spot recursive search tree implementations in the wild, in production code.

Compilers and interpreters often use recursion, and that goes to as many levels as the program requires.

Garbage collectors that use recursion to traverse the reachable objects are not unheard of.

Reference counting smart pointers are recursive. E.g. when we call object->dropReference(), and the refcount goes to zero, that may trigger otherObject->dropReference().

In C++, recursion is built into the language; e.g. destroying an object can trigger a cascade of recursive destructor calls. The object may have members which are smart pointers; those get destroyed, and may cause their referenced objects to get recursively destroyed.

Have you heard of a "recursive descent parser"? GNU C++ uses one (a huge source file written in C++, well over a megabyte long). This will recurse as deeply as the program's nesting goes; C++ programs often go to more than three levels of nesting. (There are some non-recursive hacks mixed in there, like some operator precedence parsing involving an explicit stack: Shunting-Yard or similar?)

https://github.com/gcc-mirror/gcc/blob/master/gcc/cp/parser....

Let's switch over to embedded. Have you heard of BusyBox? BusyBox provides scaled down system utilities for embedded systems. It is very widely used.

BusyBox's "libb" internal library contains a function called "recursive_action" for walking file system trees. This is actually recursive, and frequently goes more than three levels deep in actual use:

https://github.com/brgl/busybox/blob/master/libbb/recursive_...

This is used by BusyBox programs like mdev (udev replacement) lsusb, lspci, chmod, netstat, grep, tar, ...

Also, HN isn't a good place to exhibit Lisp condescension/ignorance.

You seem to be pretending that I said recursion was never useful. I can assure you I have never said any such thing.

I would never in a million years have guessed that anybody believed file system trees appear in nature. Or programming languages.

> In a sense, recursion is like object-orientedness: an elegant pattern that fits many problems, but makes a poor basis for a world view or, exclusively, a language. Lisp and Smalltalk are not sidelined because of ignorance.

In fact, in this case, the specific ignorance that Lisp isn't a "all recursion, all the time, everywhere" language family. It includes multi-paradigm languages.

You are welcome to your opinion as to why Lisp is sidelined.

There could be many reasons, such as dislike for its syntax. But that is not ignorance, just de gustibus

What I'm saying is that: the specific hypothesis that Lisp is brushed aside by some people because it has nothing to offer for repeated calculation other than the technique of recursion is necessarily a hypothesis about ignorant people. The hypothetical people hold an incorrect belief that is easy to dispel with readily available facts, which is a good working definition of ignorance. Other hypotheses may involve purely de gustibus matters; that one doesn't.

(Your wording strongly suggests that you not only believe the hypothesis but that you don't find those people ignorant.)

Reply on news.ycombinator.com