begin quoting Gabriel Sechan as of Fri, Jan 25, 2008 at 02:39:05PM -0600:
> > Quoting: [EMAIL PROTECTED]
[snip]
> > Well recursion certainly makes programs *shorter* which is a strong
> > case that they are simpler. For now I can't say that lots of
> > recursion feels simple. Lots of snakes eating their own tails and
> > program flows winding back upon themselves will take some getting
> > used to for this long time interative programmer.
>
> There's some places where it does though. Imagine you have a tree like this
Yes. I love trees and recursion. Nasty hash-tables give us O(1) access
for the win, but trees are things of beauty nevertheless. :)
> struct Node {
> int value;
> Node *leftChild;
> Node *rightChild;
> }
>
> Lets say you want to visit every node and call foo() on the value.
> Recursive solution
>
> void walkTree(Node *cur){
> if(cur == NULL)
> return;
> foo(cur->value);
> walkTree(cur->leftChild);
> walkTree(cur->rightChild);
> }
Note that this assumes that the root of the tree is a Node, rather
than having a Tree structure and a TreeNode structure, which can be
rather useful.
> An iterative solution
>
> void walkTree(Node *head){
> if(head == NULL)
> return;
> stack<Node*> toCheck;
> toCheck.push(head);
> while(toCheck.size()>0){
> Node* cur =toCheck.pop();
> foo(cur->value);
> if(cur->leftChild != NULL)
> toCheck.push(cur->leftChild);
> if(cur->rightChild != NULL)
>
> toCheck.push(cur->rightChild);
>
> }
> }
Um, no need to keep checking for NULL, that's making the code more
complicated than necessary. You waste a little space, unless your
stack implementation is smart enough to ignore pushes of NULL.
void walkTree( Node *head) {
Node *current;
stack<Node *> pending;
pending.push( head );
while( ! pending.isEmpty() ) {
if ( NULL == ( current = pending.pop() ) ) continue;
foo( current->value );
pending.push( current->leftChild );
pending.push( current->rightChild );
}
}
Branches impair readability, they should be minimized.
Also, w/r/t NULL, some trees do not have a NULL; instead, they point to
a specific node to terminate the tree, which simplifies some algorithms.
Let's say we have the listed Node structure, but what we work with is
struct Tree {
char *name;
int maxdepth;
Node *root;
Node *terminal;
}
Then our function might be
void walkTree( Tree *tree ) {
Node *current;
stack<Node *> pending;
pending.push( tree->root );
while ( ! pending.isEmpty() ) {
if ( tree->terminal == ( current = pending.pop() ) ) continue;
foo( tree->name, current->value );
pending.push( current->leftChild );
pending.push( current->rightChild );
}
}
versus
void walkTree( Tree *tree ) {
walkNodes( tree->root, tree->terminal, tree->name );
}
void walkNodes( Node *current, Node *empty, char *name ) {
if ( current == empty ) return;
foo( name, current->value );
walkNodes( current->leftChild, empty, name );
walkNodes( current->rightChild, empty, name );
}
...and we're not pushing around a lot of parameters and have two
functions, instead of one.
> The first is much simpler, as well as shorter.
Well, *somewhat* simpler.
> A good rule of thumb
> (not 100% right, but frequently is) is that recursive structures like
> trees should use recursion and iterative structures like hashes and
> arrays should use iteration.
Yup.
> The exception tends to be lists-
> they're a recursive definition of an iterative idea (an array).
> Either works quite well, although iteration is usually more efficient,
> and usually easier to read.
It also depends on what you're doing with the list. If you're going
to do something for every node in the list, iteration comes to mind;
if you're going to do something to successively smaller pieces (such
as a binary search), then recursion seems called for.
But recursion and iteration are isomorphic, so it really just comes
down to "what fits the problem definition better".
--
Canonical example is the fibonacci series
Iteration is the faster method, my dearies.
Stewart Stremler
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
