> Date: Fri, 25 Jan 2008 12:25:34 -0800
> From: [EMAIL PROTECTED]
> To: [email protected]
> Subject: Re: What is so special about recursion?
>
> On Fri, Jan 25, 2008 at 11:14:55AM -0800, David Brown wrote:
> > But there is a lot more value in constructs that are easier to reason
> > about. Problems that involve complex interacting parts are hard to reason
> > about, and therefore it is easier to have problems. Sometimes, a
> > recursively represented problem is easier to reason about
>
> 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
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);
}
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);
}
}
The first is much simpler, as well as shorter. 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.
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.
Gabe
_________________________________________________________________
Climb to the top of the charts! Play the word scramble challenge with star
power.
http://club.live.com/star_shuffle.aspx?icid=starshuffle_wlmailtextlink_jan--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
