Volume Number: 16 Issue Number: 11$ Column Tag: Mac OS X@ #Recursion: The Programmer's FriendX by Andrew C. Stonen VA programmer's bag of tricks is loaded with heuristics, algorithms and techniques, butz Vof these, few are as powerful as recursion. The Oxford English Dictionary recursively Vdefines recursion as "The application or use of a recursive procedure or definitiion"! TRecursive has the definition "Involving or being a repeated procedure such that the Vrequired result at each step except the last is given in terms of the result(s) of the Vnext step, until after a finite number of steps a terminus is reached with an outright evaluation of a result. UIn software, recursion is when a function or method calls itself, over and over, with Rslightly differing arguments. Of course this sounds like the perfect recipe for an‰ Yinfinite loop, but we will design in an exit condition so you don't end up in Cupertino! [Missing image]Recursion allows the writing of elegant and terse code once you understand how it[TOKEN:10]works. MRecursion abounds in nature, and can be visualized by thinking of the fractal SMandelbrot set - no matter how deep into the set you continue to go, the same forms Oappear over and over, in an increasingly minute, yet perfectly replicated form. KProgrammers often use a recursive data structure called a tree to represent Phierarchical data. A tree is a root (Now that's an oxyomoron!) with zero or more Tsubtrees. Each subtree consists of a root node with zero or more subtrees. A subtree Wnode with no branches or children is a leaf node. (Tree terminology uses both botanical S(root/branch) and geneological (parent/child) terms.) A classic use of recursion is Sfor tree traversal, where you want to perform some action on each node in the tree. 1

i0Figure 1. A Tree with nodes labeled postorder. TA tree can be implemented in various ways, depending on the structure and use of the‹ [tree. It's beyond the scope of this article to cover the implementation of "scales well toË Slarge N" trees such as the btree; however for a reasonably small number (e.g. underÙ S1000) of nodes, arrays of arrays will work fine. Let's define a simplistic Node as: @interface Node { : id data; // an opaque pointer to some kind of data* NSArray *_children;5 6 // if an internal node, this contains children nodes@ 4 // if this is a leaf node, it contains 0 elements.K }V // query the Node:a - (NSArray *)children;l - (NSData *)data;w // establish the Node: (- (void)setChildren:(NSArray *)newKids; - (void)setData:(id)data; @end 0And our tree controller object would look like:

No results found