4 ms·

Different strokes for different folks, as they say.

• baddox 11y ago
  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.
  • erikpukinskis 11y ago
    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.
  • dvt 11y ago
    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.
    • davexunit 11y ago
      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.
    • baddox 11y ago
      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.
      • emmelaich 11y ago
        The Fibonacci sequence is also the textbook example of how badly a naive recursive implementation can perform, because the stack explodes.
      • jonsen 11y ago
        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 ...
        • baddox 11y ago
          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).
        • bmm6o 11y ago
          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.
  • copsarebastards 11y ago
    Do you think of binary tree traversal? If so, you probably work in academia.