TweetFollow Us on Twitter

Recursion

Volume Number: 16 (2000)
Issue Number: 11
Column Tag: Mac OS X

Recursion: The Programmer's Friend

by Andrew C. Stone

A programmer's bag of tricks is loaded with heuristics, algorithms and techniques, but of these, few are as powerful as recursion. The Oxford English Dictionary recursively defines recursion as "The application or use of a recursive procedure or definitiion"! Recursive has the definition "Involving or being a repeated procedure such that the required result at each step except the last is given in terms of the result(s) of the next step, until after a finite number of steps a terminus is reached with an outright evaluation of a result."

In software, recursion is when a function or method calls itself, over and over, with slightly differing arguments. Of course this sounds like the perfect recipe for an infinite loop, but we will design in an exit condition so you don't end up in Cupertino! Recursion allows the writing of elegant and terse code once you understand how it works.

Recursion abounds in nature, and can be visualized by thinking of the fractal Mandelbrot set — no matter how deep into the set you continue to go, the same forms appear over and over, in an increasingly minute, yet perfectly replicated form.

Programmers often use a recursive data structure called a tree to represent hierarchical data. A tree is a root (Now that's an oxyomoron!) with zero or more subtrees. Each subtree consists of a root node with zero or more subtrees. A subtree node with no branches or children is a leaf node. (Tree terminology uses both botanical (root/branch) and geneological (parent/child) terms.) A classic use of recursion is for tree traversal, where you want to perform some action on each node in the tree.


Figure 1. A Tree with nodes labeled postorder.

A 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 large N" trees such as the btree; however for a reasonably small number (e.g. under 1000) 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; 
   // if an internal node, this contains children nodes
   // if this is a leaf node, it contains 0 elements.
}
// query the Node:
- (NSArray *)children;
- (NSData *)data;

// establish the Node:
- (void)setChildren:(NSArray *)newKids;
- (void)setData:(id)data;
@end

And our tree controller object would look like:

@interface TreeController {
      Node * _rootOfTreeNode;   // the root is all you need to get at any Node
}
- (void)visitNode:(Node *)node;
- (void)printData:(Node *)node;
@end

Walking a Tree: Kinds of Traversals

There are three types of tree traversals: preorder, inorder, and postorder - each defines the particulars of whether you work on a node before or after working on its children. In preorder, you work on the parent and then do an inorder traversal of each of the children . In inorder, you do a preorder traversal on the leftmost child, work on the parent, and then do an inorder traversal of each of the remaining children. In postorder, you do a postorder traversal of each of the children and then work on the parent.

Here's the code for a recursive preorder traversal:

- (void)visitNode:(Node *)node {
        NSArray *childrenToVisit = [node children];
        unsigned i, count = [childrenToVisit Count];

        // visit the current node:
       [self printData:[node data]].

       // if there are no children, then recursion ends:
        for (i = 0; i < count; i++)   // make recursive call:
   [self visitNode:[childrenToVisit objectAtIndex:i]];
}

- (void)printData:(Node *)node {
       // this is just an example - in reality you might do something useful!
      NSLog([node description]);
}

To traverse an entire tree, you would simply start the recursive process at the top of the tree by calling our method with the root node as the argument:

      [self visitNode:_rootOfTreeNode];

Note that to perform a postorder traversal, you just move the "printData" (our placeholder for the action we wish to perform on any node) to the bottom of the method:

- visitNodePostorder:(Node *)node {
        NSArray *childrenToVisit = [node children];
        unsigned i, count = [childrenToVisit Count];
        for (i = 0; i < count; i++)
   [self visitNodePostorder:[childrenToVisit objectAtIndex:i]];
        // now visit the current node:
       [self printData:[node data]].
}

Stacks and Stacks of Stacks

So how does this all work? Every programming language that supports recursion (including Objective-C) maintains a stack of information about parameters and local variables for each time a procedure, function, or method is called. When a procedure is called, the information is pushed onto the stack; when the procedure exits, the information is popped from the stack.

Given the tree pictured in Figure 1, let's mentally walk through what's happening. First we call visitNodePostorder: on the root node (node A), placing this method call on the stack. Node A has 3 children so we call visitNodePostorder on the first child (node B), pushing that call on the stack. Node B has 2 children, so we call visitNodePostorder on the first child (node C), placing that call on the stack. We then call the method on node C's first child, node D. Now the stack is 4 deep, but this final node is a leaf, so we call printData on node D. We're back in visitNodePostorder:C and the second child (node E) is called, increasing the stack to 4 again. Since it is also a leaf, we print it, pop the method call, and we're back down to 3. Now node C will print itself, and we're down to 2 deep in the stack. The second child of node B is a leaf, so we go 3 deep, and after printing, we're at 2 deep. Node B is then printed, and then we're back to the first frame in the stack (node A), on the second iteration of its for loop. Since the second child (node G) of the root node is a leaf, it gets printed, and we're on the third child. And so on for the rest of the tree.


Figure 2. Snapshots of the stack during the tree traversal.

So, you can see that the stack will grow to the depth of the tree. If you are working with very deep trees and you're concerned with implementation efficiency and want to avoid the overhead inherent in making method calls, you can remove the recursion by managing your own stack of variables. However, this results in much more complex, less elegant, less maintainable code. I'd avoid it in all but the most extreme situations.

Conclusion

As programming challenges arise, remember this recursive jewel I learned many years ago in Computer Science school: if you cannot tackle a problem, divide it into smaller problems which you can tackle. Eventually you'll have wittled the problem down to something manageable, and applying this recursive problem solving tool will usually result in a readable and maintainable software solution.


Andrew Stone <andrew@stone.com> is founder of Stone Design Corp <http://www.stone.com/> and has spent 12 years writing Cocoa software in its various incarnations.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Ember 1.8.3 - Versatile digital scrapboo...
Ember (formerly LittleSnapper) is your digital scrapbook of things that inspire you: websites, photos, apps or other things. Just drag in images that you want to keep, organize them into relevant... Read more
Apple iTunes 12.1 - Manage your music, m...
Apple iTunes lets you organize and play digital music and video on your computer. It can automatically download new music, app, and book purchases across all your devices and computers. And it's a... Read more
LibreOffice 4.4.3 - Free, open-source of...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
FoldersSynchronizer 4.2.1 - Synchronize...
FoldersSynchronizer is a popular and useful utility that synchronizes and backs-up files, folders, disks and boot disks. On each session you can apply special options like Timers, Multiple Folders,... Read more
Simon 4.0.2 - Monitor changes and crashe...
Simon monitors websites and alerts you of crashes and changes. Select pages to monitor, choose your alert options, and customize your settings. Simon does the rest. Keep a watchful eye on your... Read more
Cocktail 8.1.2 - General maintenance and...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
Cyberduck 4.6.4 - FTP and SFTP browser....
Cyberduck is a robust FTP/FTP-TLS/SFTP browser for the Mac whose lack of visual clutter and cleverly intuitive features make it easy to use. Support for external editors and system technologies such... Read more
Herald 5.0.2 - Notification plugin for M...
Note: Versions 2.1.3 (for OS X 10.7), 3.0.6 (for OS X 10.8), and 4.0.8 (for OS X 10.9) are no longer supported by the developer. Herald is a notification plugin for Mail.app, Apple's Mac OS X email... Read more
DEVONthink Pro 2.8.3 - Knowledge base, i...
Save 10% with our exclusive coupon code: MACUPDATE10 DEVONthink Pro is your essential assistant for today's world, where almost everything is digital. From shopping receipts to important research... Read more
Boom 2 1.0.1 - System-wide pro audio app...
Boom 2 is a system-wide volume booster and equalizer app that is designed especially for OS X 10.10 Yosemite. It comes with a smart interface, self-calibrates itself according to your Mac, offers... Read more

Playworld Superheroes Review
Playworld Superheroes Review By Tre Lawrence on January 30th, 2015 Our Rating: :: HERO CRAFTINGUniversal App - Designed for iPhone and iPad It’s all about the imagination, fighting bad creatures — and looking good while doing so.   | Read more »
Join the SpongeBob Bubble Party in this...
Join the SpongeBob Bubble Party in this New Match 3 Bubble Poppin’ Frenzy Posted by Jessica Fisher on January 30th, 2015 [ permalink ] | Read more »
Handpick Review
Handpick Review By Jennifer Allen on January 30th, 2015 Our Rating: :: TANTALIZING SUGGESTIONSiPhone App - Designed for the iPhone, compatible with the iPad Handpick will make you hungry, as well as inspire you to cook something... | Read more »
Storm the Halls of Echo Base in First St...
Storm the Halls of Echo Base in First Star Wars: Galactic Defense Event Posted by Jessica Fisher on January 30th, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Contradiction Review
Contradiction Review By Tre Lawrence on January 30th, 2015 Our Rating: :: SPOT THE LIEiPad Only App - Designed for the iPad Contradiction is a live action point and click adventure that’s pretty engaging.   Developer: Tim Follin... | Read more »
Unlock Sunshine Girl in Ironkill with th...
Unlock Sunshine Girl in Ironkill with this special 148Apps code Posted by Rob Rich on January 29th, 2015 [ permalink ] Robo-fighter Ironkill has been out on iOS a | Read more »
Crossroad Zombies Review
Crossroad Zombies Review By Jordan Minor on January 29th, 2015 Our Rating: :: CROSSWALKING DEADiPad Only App - Designed for the iPad Crossroad Zombies is a rough draft of a cool genre mash-up.   | Read more »
Blood Brothers 2 – Tips, Cheats, and Str...
War is hell: Is it the kind of hell you want to check out? Read our Blood Brothers 2 review to find out! Blood Brothers 2, DeNA’s follow-up to the original Blood Brothers, is an intriguing card collecting / role-playing / strategy hybrid. There’s... | Read more »
Blood Brothers 2 Review
Blood Brothers 2 Review By Nadia Oxford on January 29th, 2015 Our Rating: :: AN AGGRAVATING RELATIVEUniversal App - Designed for iPhone and iPad Blood Brothers 2 is built on a simple, solid foundation, but its free-to-play system... | Read more »
I AM BREAD, the Toast of the Town, is Ro...
Have you ever dreamt of being deliciously gluten-y? Do you feel passionate about Rye and Wheat? The guys at Bossa Studios do and that is why they are bringing I AM BREAD to iOS soon. The loafy app will feature all the new content that is being... | Read more »

Price Scanner via MacPrices.net

Intel Aims to Transform Workplace With 5th-Ge...
Intel Corporation today announced the availability of its 5th generation Intel Core vPro processor family that provides cutting-edge features to enable a new and rapidly shifting workplace. To meet... Read more
iOS App Sharalike Introduces New Instant Smar...
Sharalike slideshow and photo management software for iOS, is making it easier than ever to create shareable meaningful moments with its new instant SmartShow technology. Staying organized is a goal... Read more
Apple Becomes World’s Largest Smartphone Vend...
According to the latest research data from Strategy Analytics, as global smartphone shipments grew 31 percent annually to reach a record 380 million units in the fourth quarter of 2014. Apple became... Read more
Cut the Cord: OtterBox Resurgence Power Case...
Dead batteries and broken phones are two of the biggest issues for smartphone users today. Otterbox addresses both with the new Resurgence Power Case for Apple iPhone 6, promising to make those panic... Read more
13-inch Retina MacBook Pros on sale for up to...
B&H Photo has 13″ Retina MacBook Pros on sale for $200 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.6GHz/128GB Retina MacBook Pro: $1199.99 save $100 - 13″ 2.6GHz/... Read more
15-inch 2.5GHz Retina MacBook Pro on sale for...
 B&H Photo has the 15″ 2.5GHz Retina MacBook Pro on sale for $2319.99 including free shipping plus NY sales tax only. Their price is $180 off MSRP, and it’s the lowest price available for this... Read more
Back in stock: Refurbished iPod nanos for $99...
The Apple Store has Apple Certified Refurbished 16GB iPod nanos available for $99 including free shipping and Apple’s standard one-year warranty. That’s $50 off the cost of new nanos. Most colors are... Read more
Apple lowers price on refurbished 256GB MacBo...
The Apple Store has lowered prices on Apple Certified Refurbished 2014 MacBook Airs with 256GB SSDs, now available for up to $200 off the cost of new models. An Apple one-year warranty is included... Read more
New Good Management Suite Simplifies Enterpri...
Good Technology has announced the availability of the Good Management Suite, a comprehensive cross-platform solution for organizations getting started with mobile business initiatives. Built on the... Read more
15-inch 2.0GHz Retina MacBook Pro (refurbishe...
The Apple Store has Apple Certified Refurbished previous-generation 15″ 2.0GHz Retina MacBook Pros available for $1489 including free shipping plus Apple’s standard one-year warranty. Their price is... Read more

Jobs Board

*Apple* Solutions Consultant- Retail Sales (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Event Director, *Apple* Retail Marketing -...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global engagement strategy and team. Delivering an overarching brand Read more
At-Home Chat Specialist- *Apple* Online Stor...
**Job Summary** At Apple , we believe in hard work, a fun environment, and the kind of creativity and innovation that only comes about when talented people from diverse Read more
SW QA Engineer - *Apple* TV - Apple (United...
**Job Summary** The Apple TV team is looking for experienced Quality Assurance Engineers with a passion for delivering first in class home entertainment solutions. **Key Read more
*Apple* Retail - Multiple Positions(US) - Ap...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you re also the Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.