[btilly]

Speaking as someone who finds DP problems easy, I'd not figure it out from this approach. The way that I'd think about and tackle it in an interview is this:

1. Write a recursive solution.

2. Memoize.

If you can solve it this way, then you have a DP problem. Of course this forces you into the top down (aka recursive) approach. But in an interview, "easier to reason about" is all that matters.

Also the tradeoffs in section 5 has a mistake. Memory can and frequently does go either way. Top down can let you recognize which states you never need to think through. But a bottom up (aka iterative) approach can let you discard memory after finishing an iteration. The memory savings from that can be considerable.

[BurningFrog]

When I interviewed at $BigCompany, I really enjoyed the whiteboard programming problems I got.

But I noticed that 2/3 of them ended up with recursive solutions. Meanwhile, I spend less than 1% of my real professional programming time writing recursive code, and it's a bit silly that so much focus is on such relatively obscure technique.

[x1798DE]

I think it's a mistake to think of whiteboard problems as attempting to recreate a real work environment. They are a proxy for the kind of quality you are looking for that can be "measured" within the alotted time.

They can show that the person is prepared (they studied), generally knowledgable (they remember obscure stuff), or just clever (they come up with interesting approaches to the problem).

I'm not surprised you see both excessively simple (make sure they aren't ridiculously unqualified) and excessively obscure problems, since the first one essentially tests your reflexes and the second one tries to determine if you learned your job "by rote"

[irq11]

They’re used because “that’s what company X uses”. People are cargo culting each other, and making up post hoc rationalizations for their behavior.

Unless you work for a major tech company where optimizing the false positive rate is your primary concern, using these problems is counterproductive.

[BurningFrog]

Yeah, it's philosophically valid that you'd want to measure certain critical things that are different from the everyday grind.

But I think the simpler explanation is that these interviewers mostly had picked "cool" recursion problems.

I did get the job, and seeing $BigCompany's hiring process from the inside didn't contradict this.

[samfisher83]

You can solve most recursive problems with a loop and a stack. That way you aren't making a bunch of function calls eating up memory.

[dahart]

Ah, you beat me to it. I came to make the same suggestion.

DP is fancy caching, but you have to think about the space of the solution to do it right. It's not just easier to cache the results and use the recursive solution, but the code is often smaller and clearer too.

I spent some time understanding and coding up edit distance between trees DP-style, which is a fair bit trickier than edit distance between strings. At the end of the whole project, I wished I had simply memoized.

[bitL]

Sometimes DP problems are pretty complex in a convoluted way employing some weird tricks before you could see it the DP way; it's best to take some advanced DP problems from TopCoder or ICPC and dissect them in detail. Trivial DP problems are phased out of interviews already, unless looking for junior positions.

[blackflame7000]

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).

[jacquesm]

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.

[foota]

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.

[blackflame7000]

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.

[joefkelley]

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.

[blackflame7000]

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.

[throwaway37585]

> 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.

[kolpa]

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.

[ghettoimp]

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".

[bogomipz]

>"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?

[nordsieck]

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.

[barrkel]

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.

[FractalLP]

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.

[zodiac]

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.

[drb91]

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.

[algo646464]

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.

[oldandtired]

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".

[Silfen]

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).

[darzu]

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

[blackflame7000]

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

[danmg]

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.

[kolpa]

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.

[danmg]

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.

[blackflame7000]

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.

[danmg]

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.