5 ms·
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 stu
by 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 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).
- bmm6o 11y agoIt 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.