Hacker News Reader

I find recursion extremely intuitive, if not necessary, for pretty much any data structure with a bunch of things ("nodes") pointing to other things. That includes, most notably, linked lists and trees. I can probably work up recursive pseudocode for tree traversals pretty easily, despite not having studied computer science or doing it at work for several years, yet I find an iterative solution somewhat elusive and unnatural.

Different strokes for different folks, as they say.

I agree, but do you really think of a binary tree traversal iteratively? I won't say it's wrong, but I am extremely surprised.

No, I think about it recursively. But it hurts my brain. And to be fair, tree traversal is one of the things I find pretty intuitive about recursion.

Other stuff, not so much. Consider the Fibonacci Sequence written recursively.

I also consider the Fibonacci sequence as one of the textbook examples of a recursive problem. Even the English description of the sequence ("each new number is the sum of the last two numbers") is plainly recursive. To explain the iterative solution in English is rather difficult.

Excuse me, but I read each new number is the sum of the last two numbers as a description of iteration. You have the two last numbers from which you can then make a new.

Isn't it the recursive version which is hard to explain? The n'th Fibonacci number is the sum of ...

It depends on your perspective, which can depend on how the topic was presented. One approach (perhaps the mathematical one) is F_0 = F_1 = 1, F_n = F_{n-1} + F_{n-2}, so you generate the series 1, 1, 2, 3, 5, 8, ... That is, at the time you want F_n, you have already generated the series up to that point, and so you just add 2 numbers you already have.

On the other hand, if I ask you to compute F_1000, it might appear very recursive. You know you could make F_1000 from F_999 and F_998. And you get F_999 from... But it wouldn't be impossible to answer this question with the same approach as the first. It's not a priori obvious that "I'll calculate F_0 ... F_999" is an efficient way to calculate F_1000, but of course that turns out to be much more efficient than the naive recursive solution.

But I think Fibonacci is not the best introduction because of this. I think something like GCD calculation would be a better problem to define recursively, because there really isn't an obvious "forwards" approach to oppose the "backwards" Euclidean algorithm.

I think of "the last two numbers" as a description of recursion. You are effectively saying that the nth Fibonacci number is the sum of the (n-1)th and (n-2)th Fibonacci number, which is the textbook recursive solution.

The iterative solution is more like "start with 0 and 1, add them together to get a new number, then add that new number to the larger of the previous two numbers, and do that n times to get the nth Fibonacci number." That works just as well (or better, for computers and large n) as the recursive solution, but it's harder to explain, and it barely even hints at the most notable property of the sequence (that each number is the sum of the previous two numbers).

The Fibonacci sequence is also the textbook example of how badly a naive recursive implementation can perform, because the stack explodes.

The recursive definition is intuitive and easy to come up with given its mathematical definition. To avoid redundant computation, the function can be memoized. Yes, you can write it linearly as well, but oftentimes the linear algorithm is harder to come up with. SICP spends a lot of time on this subject in one of its early chapters and its worth a read. Also, some languages support recursion better than others. Scheme is top notch in this regard as the standards do not specify a stack, meaning that implementations can do things like heap allocate stack frames that grow and shrink according to demand.

It depends somewhat on what you are doing. If you are on a walk through a (metaphorical) forest, do you think of yourself on a subpath of a subpath of a subpath, or is it just "well I guess I'm here now!"?

If you are just doing a simple search, maybe you don't need to keep that whole stack around. An iterative approach makes a lot of sense. If you are building a map of the tree and you're not even sure what scale to make it, you might want to reserve judgement about the supertree while you explore some sub trees so you might be glad that stack is there, and you might profit from thinking about that situation as recursion.

But the answer is: yes, a lot of things you do with trees make a lot of sense as simple procedures.

Do you think of binary tree traversal? If so, you probably work in academia.

Funnily, I personally think linked lists are unintuitive.

"We have a sequential block of memory, and we want to store a sequence in it... hrm... I know, why don't we put the first element in this struct, and... I'll deal with the rest of the items elsewhere."

Linked lists would only be unintuitive if you wanted to apply them to a sequential block of memory like that. Linked lists are used in non-sequential blocks of memory, though you can use them in sequential blocks. It sometimes makes sense to, but really only in an embedded systems context where you're doing some other fun things like writing your own memory management system using preallocated arrays as heaps so that your memory usage doesn't grow unbounded.

I'm aware there are circumstances where linked lists are useful, but IMHO they're rarely introduced alongside a context that justifies them. Unintuitive doesn't mean bad, FWIW.

I wrote that after a very, very long day and long after I should've gone to bed (stupid needing to wear clothes, and not wanting to wear dirty clothes).

The main point I wanted to make was that you described linked lists as unintuitive specifically in the context of having access to sequential memory space. Linked lists are not, typically, used in that circumstance. They make much more sense, and I think become more intuitive, when you consider them in the context of non-sequential memory space.

Okay... the sequence has length measured in the billions, and we want to be able to rapidly remove its elements, or insert new elements in front of existing elements.

Suddenly linked lists (doubly-linked) are looking pretty intuitive :)

I'm not convinced. I obviously can't say what I'd do if I had to think these up, but I think I'd be more likely to try and impart ordering on a contiguous array than building a multiple-allocation one.

Going down this route would probably result in a contiguous linked list. You can argue that this is still a linked list, but I still find it conceptually more obvious. For a billion elements, it's probably also a lot faster, too.

Linked lists are just trees that only have one child on each node.

Exactly - I think storing a sequence of values in a degenerate tree is unintuitive.

You are not alone. NASA/JPL explicitly prohibits it in their coding standards [0].

  Rule 4 (recursion)
  There shall be no direct or indirect use of recursive function calls.
  [MISRA-C:2004 Rule 16.2; Power of Ten Rule 1]

  The presence of statically verifiable loop bounds and the absence of recursion 
  prevent runaway code, and help to secure predictable performance for all 
  tasks. The absence of recursion also simplifies the task of deriving reliable 
  bounds on stack use. The two rules combined secure a strictly acyclic function 
  call graph and control-flow structure, which in turn enhances the capabilities 
  for static checking tools to catch a broad range of coding defects.

[0] http://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf

Though, for context, here's the first paragraph after the introduction:

  The coding rules defined here primarily target the development of mission 
  critical flight software written in the C programming language. This means 
  that the rules are focused on embedded software applications, which 
  generally operate under stricter resource constraints than, e.g., ground 
  software.

I don't think it's at all surprising that the coding standards governing critical software running in resource-constrained environments should be so conservative. But I also don't know that the priorities motivating those standards generalize well to what most programmers do for a living.

Recursion is prohibited in embedded contexts because it allows for, potentially, unbounded growth of the call stack. In the embedded world we have to know how much space things need. You'll note they also ban malloc. But few would suggest that every C programmer should abandon malloc in their software.

> Recursion is prohibited in embedded contexts because it allows for, potentially, unbounded growth of the call stack.

Only if you're sloppy about the inputs given to the recursive code.

Recursion isn't magical. It's deterministic, and is a function of some aspect of the input values. (Corollary: If it isn't, what the fuck are you doing?)

So NASA decided to solve the stack growth problem by limiting recursion. (Zero is a limit.) It could have done the other thing and limited inputs to recursive code, which would have required more careful code analysis (static and dynamic) to figure out what the limits should be. It's an understandable decision, but don't forget it's a trade-off, and one that could have gone another way.

Sure, it's deterministic. But in embedded contexts we typically have no malloc either, and often operate in very memory constrained environments. By removing recursion and favoring iteration you know the size of your stack at any given point in program execution. There is no size range that you have to consider (for instance, by limiting recursion to a depth of 20 for a particular algorithm or something). We also have to remember that TCO is not, or historically not, guaranteed in C compilers, the language in question.

So any recursive algorithm using tail-calls would be better implemented as a for/while loop in embedded C contexts, the performance will be similar (should actually be better) and the memory is now constant instead of increasing.

Any recursive algorithms that can't use tail-calls, I'm honestly not thinking of common situations for these in an embedded context. Perhaps traversing certain data structures, but you can probably find a different data structure that will be sufficiently efficient and not require non-tail-calls. Even with sorting, if you have a small, fixed sized array you could implement a sorting network. If it's too large for that to be feasible in code, it's probably still a small enough array that insertion sort is efficient.

>It could have done the other thing and limited inputs to recursive code, which would have required more careful code analysis (static and dynamic) to figure out what the limits should be. It's an understandable decision, but don't forget it's a trade-off, and one that could have gone another way.

I don't see the trade-off.

On one hand (if you allow recursion) you need "more careful code analysis".

On the other hand, if you don't allow it, you don't lose anything. You can write the algorithm in another way, and it would be just as fast and easier to reason about.

So what's the tradeoff? It's not like recursion brings some benefit that you lose if you disallow it.

> On the other hand, if you don't allow it, you don't lose anything. You can write the algorithm in another way, and it would be just as fast and easier to reason about.

This is where we differ, then: Some algorithms are more natural to write recursively. Sorting is a big example.

I'm fairly sure Dijkstra didn't say that, since he was advocating for recursion to be added. It was one of the splinter Algol groups that added that sentence trying to remove it.

Whoops, I misunderstood, had to re-read that paragraph :)

No worries, I reread it multiple times to make sure I had it right. Not the clearest paragraph.

> It's my uninformed opinion that recursion is uninteresting and unintuitive.

Recursion is the use of the built in stack data structure that the compiler manages for you.

If you are working your way through a data set with a well determined end state that you incrementally approach (be it the end of the list, or getting closer and closer to finding a value in a tree), and you have a need to backtrack, then recursion is a good way to solve the problem.

All recursive code can be rewritten to be non-recursive, you just keep track of your own stack data structure. This can be either not that much work, or a major pain, depending on the exact problem.

> All recursive code can be rewritten to be non-recursive, you just keep track of your own stack data structure. This can be either not that much work, or a major pain, depending on the exact problem.

Bull, a function that is not primitive recursive cannot be rewritten to be non recursive.

Sources: https://en.wikipedia.org/wiki/Ackermann_function https://www.youtube.com/watch?v=i7sm9dzFtEI

> It's my uninformed opinion that recursion is uninteresting and unintuitive.

It's my informed opinion that I personally often find unintuitive things to be uninteresting, because thinking about them is less rewarding.

I wouldn't take your lack of interest to be a sign of your lack of intelligence so much as a different distribution of intuition.

I agree, I don't think I have ever used recursion in production code. You can normally avoid it by using a queue or stack data structure. Or rethinking the problem.

Haskell tutorials usually advise against explicit recursion, instead favouring combinations of map, filter etc. as the best choice, and failing that use foldl', foldr etc. With explicit recursion only being used if you really have a good reason.

I often fail recursion questions during interviews because I don't like thinking about recursion. It's too stupid and pointless to think about.

I use AWS.

I want to take my JSON, and store it in Dynamo.

I need to convert every object object embedded in my top object to a {"M" : {...}} structure, and every array/list to a {"L" : [...]} structure. So something like - {"a" : {"b" : [1]}} should become {"a" : {"M" : {"b" : {"L" : ["N" : "1"]}}}}.

The easiest way to write one function that can handle that in a generic way, no matter how complicated the data structure (barring hitting the stack limit), is recursion.

Eh. I don't think writing a custom stack implementation would be any more difficult and you'd get to scale to the memory of your machine rather than your language's runtime.

I'd love to see the code for that if you've got it (I have a recursive version in Javascript). Because the recursive one is really simple to read, intuitively grasp what is going on, confirm is correct, test, modify, etc. And rewriting it to use a stack, while possible, feels harder to me to think up, reason about, and no matter how I try comes out uglier. I haven't spent a lot of time on it, mind you (in part because the recursive one hits everything I care about), but I'd love to see one as elegant written iteratively.

Even when working with trees?

Why would you ever work on the internals of how trees work? That has 0 business value 99.99% of the time. It's all solved problems. And even so recursion might not be the best approach.

Trees don't always call themselves "trees." They can sneak up on you. Nested lists, for instance, are equivalent to trees, and nested lists show up all the time. Perhaps your programming languages has some sort of recursive map function builtin, but a lot of common languages don't, and it really helps to be able to intuitively think about recursive traversal.

Have you ever worked on a UI?

Ever?

Those are trees. Want to walk the UI to find an element? Trees. Want to manipulate the DOM? Trees.

Walk a file system?

Write a file system?

Trees and trees.

I once worked on a website that analyzed Python code in order to index it into elasticsearch for structural search queries (things like "find me all classes that inherit from SomeBaseClass"). Python's built-in ast library outputs a tree for you to traverse, and even with their provided tree walker you still deal with the internals of the tree and recursion.

Furthermore, part of our indexing needed to follow imports to find the canonical name of a value, which is a problem very well suited to a recursive solution.

You may not have encountered these situations where recursion and trees have to be dealt with, but they absolutely exist.

when did the dumbing down of programming start?

I'm all for code-reuse and componentization but common... recursion is programming 101!

Well, I imagine if your background/education wasn't computer science, and you didn't have an intro to algorithms and data structures, (and also not that into math) recursion would feel unnatural and strange.

I say this because I was originally a self-taught programmer, and I hated recursion too. Once I went to school for a CS degree, I learned how awesome it really was, and now I use it all the damn time.

I studied math and I find recursion unintuitive, whereas I find the Principle of Induction[1] profoundly intuitive (the two are very closely related).

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

So what is it about recursion that eludes you? It is very strange to me that someone would find one of those concepts easy and the other not -- as you say, they are two forms of the same thing.

I guess it's more reading and writing it in code. In my case, it makes sense to read code like I read a book: it has a beginning, a middle, and an end. (Procedural, see?)

A recursive function makes me do all these convoluted mental gymnastics when I'm just trying to figure out if Cinderella lived happily ever after or not.

I promise you, if you wrote and read more recursive functions, you would get used to them. It's just a matter of practice.

One is linear, the other recurses (things into things into things).

It's like comparing Star Wars to Inception.

If you ever develop any abstraction over the raw DOM when writing a rich web app, you'll be dealing with trees, and if your abstraction supports nesting, you'll be dealing with recursion.

Because we don't have enough new JavaScript front-end frameworks coming out every week.

Well how do you think those got solved in the first place?