Hacker News Reader

Comment by blackflame7000 | Hacker News Reader

Is recursion really worth the loss of clarity? Almost always no. The more clever you are in your code, the less likely anyone will ever see it (or want to).

View on HN

Recursion is usually clearer that iterative because it assigns names to the work being done. I find that much easier to read. Better yet: when you can state your cases separately. That's even more readable.

I don't think you represent the average coder. I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit the iterative approach is more intuitive. Especially since with a for loop you can control the number of iterations which has a number of optimization benefits. Now if its just while loops vs recursive then there's not much of a difference, however that is not the case.

Agreed. HackerNews has a greater than average amount of developers that use Haskell, F#, OCaml, Scheme, and other languages which heavily promote recursion. I'm not sure if I personally find iteration easier because I learned it first, it matches my brain better, or if it is indeed easier for most of the population.

You might be able to trace the execution of the iterative code more easily, but in my experience it is often much less clear why that produces the correct result and how that code was written in the first place.

Take a look at the wikipedia page for computing Levenshtein distance: https://en.wikipedia.org/wiki/Levenshtein_distance#Computing...

The recursive version needs barely any explanation. But ask me to carry it out by hand and I'm sure I'll pretty quickly get lost. The iterative version needs a lot more explanation for why it is the way it is, but I also think I could carry it out on paper quite easily.

I mean if you label all your variables i,j, and k and use minimal formatting or bracketing then I see your point it is harder to read. Whats complicated about an iteration. If it works properly after the first one chances are it will continue to work for the millionth one. If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a bad programmer. Conversely, you must always make sure the stopping condition and all base cases are met during recursion. Forget one corner base case and you got a rare production bug.

In an iterative solution, you have to get your loop conditions correct, and you have to create a bunch of inputs before you know how you are going to use them, sort of a "solution in search of the problem". Recursion takes a problem and expresses it terms of similar, but smaller, unsolved problems, unless you can solve it directly (base case). It's a "problem in search of a solution", that always makes progress (unless you have a bad algorithm, as always).

If a recursive solution works on a small input, it will work on a big input. If you missed a base case, you'll see it immediately because trivial (literally!) input will make your solution fail to terminate.

In production, the main problem with recursion is stack size limits (or more generally memory limits) if you can't/don't use tail-call elimination.

> Whats complicated about an iteration

What’s complicated about a recursion?

> If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a bad programmer.

> Conversely, you must always make sure the stopping condition and all base cases are met during recursion.

You seem to be applying a double standard here.

> Forget one corner base case and you got a rare production bug.

Base cases are usually much easier to reason about.

Then why does NASA consider it unsafe for mission critical code?

How about unknown potential stack size?

How about factoring a large number with recursion?

Everything recursive can be transformed to iterative and yea sometimes it’s not as sexy but neither is a helmet

https://www.reddit.com/r/programming/comments/3dnsh1/nasas_t...

> Then why does NASA consider it unsafe for mission critical code?

They also proscribe unbounded iterations (point 2). In any case, NASA’s guidelines for mission-critical code are not necessarily good guidelines for general software engineering, given the constraints involved.

It’s also worth noting that recursive solutions are probably more amenable to static analysis and automated theorem proving.

> How about unknown potential stack size?

If stack size is a problem, try an iterative solution.

> How about factoring a large number with recursion?

Go with iteration.

You keep editing your answer to add more cases where iteration is the way to go. I’m not disputing there are use cases where iteration is appropriate.

> Then why does NASA consider it unsafe for mission critical code?

More like they're using an old Fortran 77 environment which doesn't support recursive functions.

More like they were using C, saw the prospect of unbounded stack calls unreasonable with a computer with limited ram and banned recursion. Oh wait that's exactly what happened because iteration is safer than recursion.

Iteration is not inherently safer than recursion. NASA also banned while(true) iteration. The important part is "fixed upper bounds".

"Give all loops a fixed upper bound. It must be trivially possible for a checking tool to prove statically that the loop cannot exceed a preset upper bound on the number of iterations. If a tool cannot prove the loop bound statically, the rule is considered violated."

https://pdfs.semanticscholar.org/ad40/26510beb1a309902704583...

The static analysis tools have a harder time parsing the upper bounds on recursive functions, and so do the engineers doing the code reviews for similar reasons.

This isn't just a NASA thing. Pretty much any embedded coding standard says the same thing. The JSF C++ standard, and MISRA-C I know both do as well, just off the top of my head.

No that's incorrect. Their rules are C guidelines, and they are easy to Google. You might want to do that before making assumptions.

NASA's rules, the ones being referenced above, are designed for safety. They require code to be easy to statically analyze and to have absolutely predictable behavior.

Also to be avoided: memory allocation, unbounded loops, function pointers, preprocessor macros.

https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev...

Most of the numerical code they're going to use is in Fortran, and interlanguage calling convention and the runtime might pose a problem.

This is in addition to not using recursive functions being pretty standard in anything embedded. Early computers and embedded systems had very limited stack space or had calling conventions that made recursion impossible.

> Most of the numerical code they're going to use is in Fortran, and interlanguage calling convention and the runtime might pose a problem.

The rationale they used for these rules was written down. It has nothing to do with Fortran. I've offered links that you can read. You're making more assumptions. If there's C-to-Fortran calling at all, then recursion presents zero extra difficulty. Once you can make any function call, you can make all function calls.

> This is in addition to not using recursive functions being pretty standard in anything embedded.

It's true that for small embedded devices, recursion is not used often. It's also true that function pointers and heap allocations and unbounded loops are generally avoided too. Though, often main() in an embed is a white(true){} loop. I wouldn't be surprised to see that at NASA.

One could argue that all of these 10 NASA rules represent some standard practice in embedded code and/or some degree of common sense. They're not claiming to be new or non-standard or unintuitive or innovative; they simply wrote down what people agreed are best practices.

That's a restriction on the environment which has absolutely nothing to do with how readable a certain piece of code is. In fact it argues the opposite: we force you to use a less readable version of your code because the elegant one may be easier to read but it may have negative consequences due to implementation details.

That's a really good trade-off for them but it does not necessarily help readability.

But then your code is not portable because it is now susceptible to arbitrary stack depth changes blowing up your program. None of your arguments make sense when compared with the overwhelmingly superior iterative approach. Recursion is the same as iteration + downsides. I mean seriously name the last time you had a stack overflow and weren't doing recursion? That's an entire class of bug introduced or eliminated by a simple design decision. That's how you write superior code for now and in the future.

You shouldn't have to know about the implementation when writing portable code. If you introduce recursion, you now need to worry about implementation since the machine max stack size is now an issue and you've broken the abstraction. And what exactly did you gain that outweigh's the cons?

You are confusing implementation of a language with readability. And I honestly don't remember the last time I had a stack overflow, there is something known as tail-call optimization.

https://en.wikipedia.org/wiki/Tail_call

Then why does NASA consider it unsafe for mission critical code?

You started with the assertion iterative implementations were more intuitive and easier to read so this is a bit of goalpoast-moving. Write an iterative pseudocode DFS or quicksort. How 'intuitive' does that look?

I'm saying that there are so many downsides both obvious and sneaky associated with recursion that it makes almost no sense to use when the iterative approach is usually safer, doesn't have the headache of unbounded stack calls, and can be more easily parallelized with things like OpenMP

That's what you are saying now, this is what you were saying before:

" I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit the iterative approach is more intuitive. "

Now you are at NASA sending probes to asteroid Weasel 39812.

> > Whats complicated about an iteration

> What’s complicated about a recursion?

Especially as iteration is just a special case of recursion :)

Very much agree.

If you are working on any kind of tree structure, graph, parse tree, etc., recursion can be really beautiful and clear.

My theory: folks like iteration because 90% of the "for" loops they write are really just "foreach".

>"folks like iteration because 90% of the "for" loops they write are really just "foreach"."

I didn't understand this comment. What do you mean by "for vs foreach."? Can you elaborate?

I guess the foreach is where each iteration has independent operation, vs a generic for loop where this iteration depends on result of the previous iterations.

It really depends on the kind of problem. For example, recursive solutions to linked-list/tree/graph problems are typically substantially easier to understand than their iterative counterparts, in large part because the data structures themselves are recursively defined.

It's only more intuitive to see the shape of the serial execution. That same property makes it more difficult to prove qualities about the code (say, correctness) because you need to keep track of state in your head as you trace through the program, rather than encoding it structurally as you would with a recursive solution.

So, intuitive is not so valuable unless you get correctness out of it.

Depends on the problem. Some problems have very explicit recursive structure (eg http://rosettacode.org/wiki/Arithmetic_evaluation) such that an iterative solution is more "unnatural". Not saying that most problems are like that, just that this shows it depends on the problem.

Most recursive functions have a tree structure, either in the control flow or data flow. For loops don't really cut it; you minimally need auxiliary storage to track which branch you're currently on for every ancestor level, either explicitly by pushing indexes or structures onto a stack or queue, or implicitly with a work stack or queue. That's a bunch of accounting in an iterative solution you don't need with a recursive solution. The iterative solution will end up harder to read as a result. It'll also be a lot harder to reason about if the tree-like structure of the code is obscured.

If you need to return values for processing each child, and integrate them at the parent, then your solution gets tougher to reason about, as there's an ordering constraint and a dependency.

Recursion doesn't come up super often in most domains, but it's not rare. E.g. doing anything non-trivial with the DOM in a web front end, parsing an XML or JSON document, etc.

You generally need to be familiar with making arguments about aggregate complexity (e.g., every element will only be visited X times because... so the complexity is O(N)) to show complexity for a recursive solution, as opposed to the iterative solution where the complexity is generally more apparent ime.

All dynamic programming algorithms are recursive. They are essentially a (constructive) proof by induction.

For clarity, perhaps one can include a "proof of correctness" of the algorithm in the comments.

There are problems that have clearer solutions when expressed as recursive. There are problems that have clearer solutions when expressed as iterative.

Having both tools in your toolbox and knowing when to use each is part and parcel of developing yourself as a craftsman or craftswomen programmer.

In addition, being able to know when to use memoing in producing your solution is another tool to be put in your toolbox.

Yes, every recursive function has an iterative solution, but the iterative solution can be far more complex. The best example of this is that lovely little function - Ackermann-Peter function. The recursive version is just a few lines long. The iterative version is quite a few pages long.

There are specific schemas in which the recursive form should be rewritten as an iterative solution. You can find these detailed in such old gems of books like "Algorithms + Data Structures = Programs".

It depends on the particulars of a problem, but structural recursion is often substantially clearer. One reason is that it enables more abstract reasoning about the behavior of an algorithm. You can reason like you would for an induction proof, instead of mentally executing steps in a loop (denotational vs. operational).

Why are you assuming that the recursive solution is less clear?

Experience, tells me so. To be fair some items like Fibonacci numbers are probably equally as clear.

Divide an conquer type algorithms usually lend themselves to naive recursive solutions more often than not. DP usually requires you to find that solution and find some clever relationships that allow you to build up the final solution from the bottom up.

Sure there are some problems that lend themselves nicely I already said as much. But in general for an INTERVIEW problem, it as a poor skill to dwell on or even bother testing for since real-world coding is simply not done that way or God forbid what might happen when someone not as capable (but cheaper or younger) has to take over your code base.

We're talking about ACM style search problems that are used for interviews, and not about iterating over an array recursively. For these, the recursive formulation is the naive and inefficient way of solving them.

If you systematically analyze it, you don't need to be clever on a per-problem basis. Every recursive solution can me methodically converted to DP.

Yes, it's a form of pattern recognition. You can get very good at it and do it mechanically, just like solving integrals.

You can spend a lot of time getting very good at them, or you can just use memorization/rsolve just like you can just use maple or evaluate them numerically for integrals.

Reply on news.ycombinator.com