Re^4: Is deep recursion bad?

Recursion is well suited only for depth-first and iterative deepening depth-first search strategies.

Once you advance pass toy problems as the Towers of Hanoi and start solving problems that require better strategies, you learn that just using directly the built-in support for recursion on the language to implement a search (or some other related operations) is not always a good idea because then, later, there is no way to change the algorithm without rewriting it fully.

A more open approach is to keep the state of the explored problem space in an explicit data-structure (in contra-position to keeping it implicitly on the language stack as built-in recursion does). Then, you can change the search strategy just changing that data structure (i.e. FIFO => breadth-first, LIFO => depth-first, queue => best-first, etc.)

Note that I don't see a great difference between iteration and linear-recursion, as they are equivalent, even if sometimes expressing an algorithm in the recursive way is simpler. For me the breaking point is having unbounded tree-like recursion or not.

In the particular case of your iterative implementation of the Towers of Hanoy that's utterly complex, the problem is that you are being too clever. You are avoiding to keep the state because for that particular problem it is possible to derive it just from the iteration counter.

Also, the strategy you use to solve the problem is hard-coded. What would happen if for instance, there were 4 sticks instead of 3, could you modify it to provide the best solution (that which minimizes the number of moves) easily? what if every disk could only be placed in a given subset of the sticks?

Comment on Re^4: Is deep recursion bad?

Replies are listed 'Best First'.
Re^5: Is deep recursion bad? by Anonymous Monk on May 09, 2015 at 11:00 UTC
Hi, That's exactly my point, which you seem to be missing. I'm nowhere trying to be smart, but only to show that even for a simplistic problem as the classical 3-poles Hanoi Tower, getting an iterative solution than does better than the iterative counterpart, that is NOT mimic a call stack in any way (since in that event, you better off with the recursive approach in the first place), is a hell of a proposition, as you can see (my personal solution, not yet published, does not use a stack, is sound by design, but utterly complex). Therefore this is my point : general recursive functions (whether implemented thru the built-in support of the language or thru functional continuations to render the stack explicit and provide potential for applying various traversal strategies) are not only powerful in their abilities to capture complex algorithms, but sometimes unavoidable when the iterative counterpart (which does not mimic a stack) is too complex or even not known (egAckerman iterative is not known). In conclusion, one should not conceive recursion as limited to what built-in support actual languages offer, but as an abstract conceptual tool, as it is with pure FP. This is the point I wanted to emphasize on a simple example. Cheers	[reply]

Replies are listed 'Best First'.

Re^5: Is deep recursion bad?
by Anonymous Monk on May 09, 2015 at 11:00 UTC

Hi, That's exactly my point, which you seem to be missing. I'm nowhere trying to be smart, but only to show that even for a simplistic problem as the classical 3-poles Hanoi Tower, getting an iterative solution than does *better* than the iterative counterpart, that is NOT mimic a call stack in any way (since in that event, you better off with the recursive approach in the first place), is a hell of a proposition, as you can see (my personal solution, not yet published, does not use a stack, is sound by design, but utterly complex). Therefore this is my point : general recursive functions (whether implemented thru the built-in support of the language or thru functional continuations to render the stack explicit and provide potential for applying various traversal strategies) are not only powerful in their abilities to capture complex algorithms, but sometimes unavoidable when the iterative counterpart (which does not mimic a stack) is too complex or even not known (egAckerman iterative is not known). In conclusion, one should not conceive recursion as limited to what built-in support actual languages offer, but as an abstract conceptual tool, as it is with pure FP. This is the point I wanted to emphasize on a simple example. Cheers

[reply]