[dirtybird04]

Went through interview rounds last year and I was asked a recursion questions for a DS interview. Been doing this for 10 years and have never come across a data problem that only recursion could solve. But I remembered it from university days, so I cobbled together a working answer.

At the end of the interview, I asked the interviewer to give me one scenario where a recursive solution would be the most efficient one. Blank stares.

That was my eye-opening moment. I would never work for a place that asks these ridiculously outdated copy-paste interview questions. Can't believe I put up with that shit for so long.

[balfirevic]

> Been doing this for 10 years and have never come across a data problem that only recursion could solve

That makes sense - there are no such problems (which is obvious if you consider the fact that Turing machines don't have recursion - nor functions, for that matter).

> I asked the interviewer to give me one scenario where a recursive solution would be the most efficient one

That also makes sense, as recursion usually isn't a technique that will bring an efficiency edge over non-recursive technique. It might often bring maintainability and understandability edge, though.

Solving the problem using recursion highlights the fact that it has, well, a recursive solution - which means that the solution can be expressed as a set of operations on top of solution to a smaller instance of the original problem. This can be an important property to notice about a problem, whether or not you're going to solve it with the function that calls itself.

Additionally, some problems have a solution that can be nicely expressed as a set of mutually recursive functions (instead of just a single recursive function). These are harder to express non-recursively. Many parsers are written like this, for example the C# parser: https://news.ycombinator.com/item?id=13915150

[_clhx]

It would be more difficult to read and maintain any solution to many problems where you are operating on nested objects, especially if the nesting is more than a few levels deep or even arbitrarily deep, without using recursion. Also generating such objects, such as with nested parentheses, is easier as well.

[yunohn]

>> one scenario where a recursive solution would be the most efficient one

Funnily enough, this is also what made me stop the Scala Coursera midway. They focus way too much on converting various problems into Tail-call recursion because Scala can optimize them.

[failwhaleshark]

That's the way to do it. Carefully dissect the ambiguous signals potential employers emit throughout their process, and form an impression around the time of an offer so you know if you'd keep negotiating.

Too often, the interviewers are just trying to emulate seeming smart out of some ego thing, haven't been trained how to interview and just emulate what they think they're supposed to do, or are too lazy to ask real-world questions.

IIRC from CS, every recursion problem can be turned into an iterative one. Even many production compilers contain handmade parsers are recursive primarily for maintainability, not for technical reasons. There are plenty of ways to make bottom-up parsers (LALR parser generators) that don't use recursion but they aren't as useful at generating diagnostics, especially explaining parse error reasons in human-readible language.

Also: https://knowyourmeme.com/memes/im-getting-too-old-for-this-s...