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

Monolingual 1.6.4 - Remove unwanted OS X...
Monolingual is a program for removing unnecesary language resources from OS X, in order to reclaim several hundred megabytes of disk space. If you use your computer in only one (human) language, you... Read more
CleanApp 5.0 - Application deinstaller a...
CleanApp is an application deinstaller and archiver.... Your hard drive gets fuller day by day, but do you know why? CleanApp 5 provides you with insights how to reclaim disk space. There are... Read more
Fantastical 2.0 - Create calendar events...
Fantastical is the Mac calendar you'll actually enjoy using. Creating an event with Fantastical is quick, easy, and fun: Open Fantastical with a single click or keystroke Type in your event details... Read more
Cocktail 8.2 - General maintenance and o...
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
Direct Mail 4.0.4 - Create and send grea...
Direct Mail is an easy-to-use, fully-featured email marketing app purpose-built for OS X. It lets you create and send great looking email campaigns. Start your newsletter by selecting from a gallery... Read more
jAlbum Pro 12.6 - Organize your digital...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code!... Read more
jAlbum 12.6 - Create custom photo galler...
With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly, with pro results Simply drag and drop photos into groups, choose a design... Read more
Lyn 1.5.9 - Lightweight image browser an...
Lyn is a lightweight and fast image browser and viewer designed for photographers, graphic artists and Web designers. Featuring an extremely versatile and aesthetically pleasing interface, it... Read more
Sublime Text 3080 - Sophisticated text e...
Sublime Text is a sophisticated text editor for code, markup, and prose. You'll love the slick user interface, extraordinary features, and amazing performance. Goto Anything. Use Goto Anything to... Read more
WALTR 1.0.11 - Drag-and-drop any media f...
WALTR is designed to make it easy to upload and convert any music or video file to an iPad or iPhone format for native playback. It supports a huge variety of media file types, including MP3, MP4,... Read more

Bio Inc's New Expansion is Infectin...
Bio Inc., by DryGin Studios, is the real time strategy game where you infect a human body with the worst virus your evil brain can design. Recently, the game was updated to add a whole lot of new features. Now you can play the new “Lethal”... | Read more »
The Monocular Minion is Here! Despicable...
Despicable Me: Minion Rush, by Gameloft, is introducing a new runner to the mix in their latest update. Now you can play as Carl, the prankster minion. Carl has a few new abilities to play with, including running at a higher speed from the start.... | Read more »
Dungeon of Madness (Games)
Dungeon of Madness 1.0.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.0 (iTunes) Description: Dungeon of Madness is an action game where you rotate tiles to create our own route. Help the hero by connecting the... | Read more »
Filters for iPhone (Photography)
Filters for iPhone 1.0 Device: iOS iPhone Category: Photography Price: $.99, Version: 1.0 (iTunes) Description: | Read more »
Jump'N'Shoot Attack (Games)
Jump'N'Shoot Attack 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: A mobile game for gamers! Join Louise Lightfoot, the legendary "Master of Jumping and Shooting", on her mission to save... | Read more »
Space Bounties Inc. (Games)
Space Bounties Inc. 1.4 Device: iOS Universal Category: Games Price: $1.99, Version: 1.4 (iTunes) Description: SuperGameDroid: 4/5 "Satisfying futuristic RPG combat, high replay value, and a heavy dose of nostalgia make Space... | Read more »
Gamebook: Pocket RPG (Games)
Gamebook: Pocket RPG 1.0.11 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.11 (iTunes) Description: Walk into the Land of Lanthir Lamath ruled by wicked skeletons and fight for your life in a thrilling adventure.... | Read more »
Kids Can Mix, Match, and Catch with Tata...
Tatadada MixMatch, by Tatadada Ltd, is a mobile version of the classic game of mix & match. The game uses brightly colored creatures to train your children's pattern matching skills and hand-eye coordination. It's aimed at children around age 5... | Read more »
The Trace: Murder Mystery Game (Games)
The Trace: Murder Mystery Game 1.2.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.2.0 (iTunes) Description: | Read more »
This Week at 148Apps: March 16-20, 2015
Spring Roars In At 148Apps How do you know what apps are worth your time and money? Just look to the review team at 148Apps. We sort through the chaos and find the apps you're looking for. The ones we love become Editor’s Choice, standing out above... | Read more »

Price Scanner via MacPrices.net

Logitech Says MX Master Is Its Most Advanced...
Logitech’s new MX Master Wireless Mouse incorporates the best of Logitech’s many computer mouse innovations into a striking hand-sculpted design. The company claims that the MX Master creates a new... Read more
Save up to $300 on a new Mac, $30 on an iPad,...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
Apple refurbished 2014 MacBook Airs available...
The Apple Store lowered prices on Apple Certified Refurbished 2014 MacBook Airs recently, with models now available starting at $679. An Apple one-year warranty is included with each MacBook, and... Read more
Mac Notebook Evolution; A Desktop Replacement...
More often than not right from the beginning, Apple’s Macs have tended to skew toward small. The original Macs were called “compacts,”, and notwithstanding a few exceptions like the honking Big Mac... Read more
13-inch 1.4GHz/128GB MacBook Air (Apple refur...
The Apple Store has Apple Certified Refurbished 2014 13″ 1.4GHz/128GB MacBook Airs available for $759 including free shipping plus Apple’s standard one-year warranty. Their price is $240 off original... Read more
YEP! Alternative Browser for iOS Now Supports...
Pfaeffikon, Switzerland based Power App AG has announced the release of an update to their Yep! Web Browser (v1.3.0) for iOS8 iPhone and iPad. Yep! hit the App Store shortly after the release of iOS... Read more
15-inch Retina MacBook Pros on sale for up to...
B&H Photo has the new 2014 15″ Retina MacBook Pros on sale for up to $250 off MSRP for a limited time. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $... Read more
Clearance 13-inch Retina MacBook Pros availab...
B&H Photo has leftover 2014 13″ Retina MacBook Pros on sale for up to $250 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.6GHz/128GB Retina MacBook Pro: $1098... Read more
Clearance 2014 MacBook Airs on sale for up to...
B&H Photo has MacBook Airs on sale for up to $180 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 11″ 128GB MacBook Air: $789.99 110 off original MSRP - 11″ 256GB... Read more
Apple refurbished Time Capsules available for...
The Apple Store has certified refurbished Time Capsules available for $100 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $199, $100... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - D...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Systems Engineer - Pre Sales, Educat...
…is responsible for proactively providing technical expertise to drive sales of Apple solutions into assigned accounts. The SE architects, validates, and assists in Read more
Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.