25 messages in org.ibiblio.lists.xom-interest[XOM-interest] Recursion
FromSent OnAttachments
Wolfgang HoschekFeb 9, 2004 6:42 pm 
Elliotte Rusty HaroldFeb 10, 2004 9:25 am 
Wolfgang HoschekFeb 10, 2004 3:23 pm 
jco...@reutershealth.comFeb 10, 2004 3:48 pm 
Elliotte Rusty HaroldFeb 11, 2004 1:21 pm 
Wolfgang HoschekFeb 11, 2004 1:24 pm 
jco...@reutershealth.comFeb 11, 2004 2:15 pm 
Elliotte Rusty HaroldFeb 11, 2004 3:18 pm 
jco...@reutershealth.comFeb 11, 2004 4:20 pm 
Francois BeausoleilFeb 11, 2004 8:08 pm 
Trimmer, ToddFeb 12, 2004 11:57 am 
Elliotte Rusty HaroldFeb 12, 2004 2:53 pm 
Trimmer, ToddFeb 13, 2004 1:26 pm 
Elliotte Rusty HaroldMar 8, 2004 3:17 pm 
jco...@reutershealth.comMar 8, 2004 4:06 pm 
Elliotte Rusty HaroldMar 8, 2004 4:34 pm 
Elliotte Rusty HaroldMar 9, 2004 11:55 am 
Bradley S. HuffmanMar 9, 2004 12:09 pm 
Elliotte Rusty HaroldMar 9, 2004 1:05 pm 
jco...@reutershealth.comMar 9, 2004 2:04 pm 
jco...@reutershealth.comMar 9, 2004 4:32 pm 
Elliotte Rusty HaroldMar 9, 2004 10:43 pm 
John CowanMar 9, 2004 10:58 pm 
Elliotte Rusty HaroldMar 10, 2004 6:12 am 
Dirk BergstromMar 10, 2004 6:25 pm 
Actions with this message:
Paste this link in email or IM:
Paste this link in email or IM:
Atom feed for this thread
Paste this URL into your reader:
Subject:[XOM-interest] RecursionActions...
From:jco...@reutershealth.com (jco@reutershealth.com)
Date:Mar 8, 2004 4:06:24 pm
List:org.ibiblio.lists.xom-interest

Elliotte Rusty Harold scripsit:

That algorithm was: 1) firstChild, unless null, in which case 2) nextSibling, unless null, in which case 3) parent() and try again, unless root, in which case 4) stop.

Sorry, that wasn't too clear. Let me try that again:

0) Move to the root node. 1) Process the current node. 2) If the current node has a child: move to the first child, go to step 1. 3) If the current node has a rightward sibling: move to the rightward sibling, go to step 1. 4) If the current node has a parent: move to the parent, go to step 2. 5) Done.

This does preorder processing (parents before children). Provided there are O(1) ways to find the first child, right sibling, and parent, this is slightly more time-efficient than recursion, and its stack consumption is O(1).

For processing other than from the root node, you eliminate step 0 and change step 4 to "If the current node is not the initial node".

-- John Cowan jco@reutershealth.com www.reutershealth.com www.ccil.org/~cowan If a soldier is asked why he kills people who have done him no harm, or a terrorist why he kills innocent people with his bombs, they can always reply that war has been declared, and there are no innocent people in an enemy country in wartime. The answer is psychotic, but it is the answer that humanity has given to every act of aggression in history. --Northrop Frye