Re: factorial n! program

blmblm@xxxxxxxxxxxxx wrote:
In article <efak4o$apr$1@xxxxxxxxxxxxxxxxx>,
....
There are better ways to make recursion interesting. Think
of a binary tree you have set up, and now want to visit all
the nodes. [...]

Indeed! exactly the examples I use to try to convince hardened
"wouldn't it be easier to just write a loop?" types ....

That's one of the examples I always use to point out the
advantages of not doing recursion. A depth-first tree
traversal is just a loop around a stack. If you use recursion,
the stack is automatic and the code is barely a little simpler.
The loop form is usually noticably faster.

But, suppose you want to traverse the tree width-first? The
loop-based algorithm is easy to modify: replace the stack
with a queue. That's all you do. You're still guaranteed to
traverse the whole tree (and it uses less space than depth-first
if the tree is narrow and deep). How do you do that with
recursion?

Suppose you want to traverse the loop in some other order
by prioritizing the subtrees (say, by the likelyhood of finding
an interesting node - a common thing in game trees), you sort
the queue between steps (or use the partial order that's used
by heapsort) so the next node is the highest priority. How
do you do that with recursion?

The fact is that recursion hides the fact that different search
orders are symmetric with depth-first based on what intermediate
store you use for the nodes that have yet to be traversed. This
biases your approach to solving problems involving trees.

--
J. Giles

"I conclude that there are two ways of constructing a software
design: One way is to make it so simple that there are obviously
no deficiencies and the other way is to make it so complicated
that there are no obvious deficiencies." -- C. A. R. Hoare


.

Relevant Pages

  • Re: Defence of recursive programming
    ... less fundamental) than either iteration than recursion. ... depending on whether you're first-time into the loop or in a ... Robinson about recursive tree traversals, ...
    (comp.lang.functional)
  • Re: Depth First Search traversal of this list
    ... I am trying to traverse the list C)) in a way that the ... works by iterating over the items at one level in the tree. ... are deferred into a queue, which is processed after the atoms are visited. ... After collecting both the queue and current level items, we do the recursion to ...
    (comp.lang.lisp)
  • Re: Count all nodes in a treeview
    ... Which suggests that the TTreeNodes type exposes the entire tree as a flat hierarchy via its "Item" member. ... Pedro's code does this via recursion, returning for each node the sum of the number of direct descendants and the calculated value of nodes from each of those descendants. ... child I traverse the childnode and get all of it's settings too. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Searching "Binary Search Trees" using recursion.
    ... >every single leaf on the tree. ... it's hard *not* to use recursion. ... >statements, and if i use return statements, i cant call iself twice. ... int countNodes(BstNode subtreeRoot) { ...
    (comp.lang.java.help)
  • Re: Binary Tree reposted
    ... > linked lists at all the tree nodes. ... //but I feel this is "look ahead recursion" and inferior to the above. ... If it's not clear, maybe your instructor ...
    (comp.lang.pascal.delphi.misc)