7 ms·
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 inclu
by baddox 11y ago
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.
- dvt 11y agoDifferent strokes for different folks, as they say.
- baddox 11y agoI agree, but do you really think of a binary tree traversal iteratively? I won't say it's wrong, but I am extremely surprised.
- erikpukinskis 11y agoIt 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.
- dvt 11y agoNo, 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.
- davexunit 11y agoThe 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.
- baddox 11y agoI 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.
- emmelaich 11y agoThe Fibonacci sequence is also the textbook example of how badly a naive recursive implementation can perform, because the stack explodes.
- jonsen 11y agoExcuse 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 ...
- baddox 11y agoI 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).
- copsarebastards 11y agoDo you think of binary tree traversal? If so, you probably work in academia.
- Veedrac 11y agoFunnily, 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."
- Jtsummers 11y agoLinked 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.
- Veedrac 11y agoI'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.
- Jtsummers 11y agoI 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.
- Retra 11y agoLinked lists are just trees that only have one child on each node.
- 11y ago