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

Logitech Control Center 3.9.2 - Keyboard...
Logitech Control Center (LCC) is designed to support OS X and allows you to take full advantage of your Logitech keyboard, mouse, or trackball. With the LCC you can: Browse the Internet using... Read more
Adobe Acrobat Pro 15.007.20033 - Powerfu...
Acrobat Pro DC is available only as a part of Adobe Creative Cloud, and can only be installed and/or updated through Adobe's Creative Cloud app. Adobe Acrobat Pro DC with Adobe Document Cloud... Read more
CleanMyMac 3.0.1 - Delete files that was...
CleanMyMac makes space for the things you love. Sporting a range of ingenious new features, CleanMyMac lets you safely and intelligently scan and clean your entire system, delete large, unused files... Read more
Evernote 6.0.10 - Create searchable note...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
CleanApp 5.0.1 - Application deinstaller...
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
Quicken 2015 2.5.0 - Complete personal f...
Quicken 2015 helps you manage all your personal finances in one place, so you can see where you're spending and where you can save. Quicken automatically categorizes your financial transactions,... Read more
Tonality Pro 1.1.4 - Professional-grade...
Tonality Pro gives you the power to create stunning and dramatic black & white images. This is a complete monochrome image editor with more than 150 one-click style presets, totally unique... Read more
Adobe Photoshop CC 2014 15.2.2 - Profess...
Photoshop CC 2015 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Photoshop customer). Photoshop CS6 is still available for purchase (... Read more
BBEdit 11.1 - Powerful text and HTML edi...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more
Together 3.4.3 - Store and organize all...
Together helps you organize your Mac, giving you the ability to store, edit and preview your files in a single clean, uncluttered interface. Smart storage. With simple drag-and-drop functionality,... Read more

The Enchanted Cave 2 (Games)
The Enchanted Cave 2 2.1 Device: iOS Universal Category: Games Price: $2.99, Version: 2.1 (iTunes) Description: Delve into a strange cave with a seemingly endless supply of treasure, strategically choosing your battles to gather as... | Read more »
Crystal Siege is on Sale With a New Univ...
Crystal Siege,  FDG Entertainment's RPG  Tower Defense game, has gone universal in its latest update. [Read more] | Read more »
Oh My Pixel! We Go Hands-on With The Kni...
I recently had a chance to play around with the upcoming Knights of Pen & Paper 2 from Paradox Interactive. I was a huge fan of the first game, so I had a lot of expectations going into it - and I wasn't disappointed. The game has gotten some... | Read more »
Throw Out Your Stylus and Sketch With Pe...
Penpoint Drawing, by Damin Liu,  is a new creative drawing app that uses your finger as your stylus. [Read more] | Read more »
Oceanhouse has Released Just So Thankful...
Oceanhouse Media, makers of digital book apps, are celebrating Mother's Day with a giveaway and a new app. [Read more] | Read more »
Get Dressed, the Virtual Wardrobe App fo...
Dressed, by  Kabuki Vision, is one of the first fashion apps for the Apple Watch. It pairs your watch with your iPhone to let you browse garments from your closet and mix and match them to create the perfect outfit. To add new pieces you just use... | Read more »
Show Everyone Who the Pack Master is in...
HeroCraft has added the new PvP Arena mode to  Warhammer 40,000: Space Wolf. Now you'll be able to go up against wolves around the world in intense  3-v-3 battles. As you battle the stages will get harder, but you'll get amazing rewards and climb... | Read more »
Jurassic World: The Game - Tips, Tricks,...
You’ve probably already got a huge and incredibly popular theme park in Jurassic Park Builder. That’s great, but Jurassic World: The Game is a slightly different beast. This time around you’ll be spending a lot more time in the Arena, and will have... | Read more »
Battledots (Games)
Battledots 1.00 Device: iOS Universal Category: Games Price: $.99, Version: 1.00 (iTunes) Description: Battledots is an intense, fast-paced strategy game where you must attack the opponent while defending your base, and everything is... | Read more »
Stella's Journey (Games)
Stella's Journey 1.1 Device: iOS Universal Category: Games Price: $2.99, Version: 1.1 (iTunes) Description: "The concept is neat and fun to play around with" - TouchArcade"Aside from looking fantastic, the game offers some very... | Read more »

Price Scanner via MacPrices.net

Sale! New 13-inch 256GB MacBook Air for $1099...
B&H Photo has the new 2015 13″ 1.6GHz/256GB MacBook Air on sale for $1099.99 including free shipping plus NY tax only. Their price is $100 off MSRP. Read more
Japan Post Group, IBM and Apple Deliver iPads...
Japan Post Group, IBM and Apple executives meeting in in New York City yesterday announced a first-of-its-kind initiative aimed at improving the quality of life for millions of Japanese senior... Read more
Worldwide Tablet Market Contracts For Second...
Worldwide tablet shipments recorded a second consecutive quarter of year-over-year decline in the first calendar quarter of 2015 (1Q15), according to preliminary data from the International Data... Read more
Apple restocks refurbished Mac minis for up t...
The Apple Store has restocked Apple Certified Refurbished 2014 Mac minis, with models available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz... Read more
13-inch 2.5GHz MacBook Pro available for $999...
Adorama has the 13-inch 2.5GHz MacBook Pro on sale for $999 including free shipping plus NY & NJ sales tax only. Their price is $100 off MSRP. Read more
New 13-inch Retina MacBook Pros available for...
Save up to $80 on the purchase of a new 2015 13″ Retina MacBook Pro at the following resellers. Shipping is free with each model: 2.7GHz/128GB MSRP $1299 2.7GHz/256GB... Read more
15-inch 2.2GHz Retina MacBook Pro (Apple refu...
The Apple Store has restocked Apple Certified Refurbished 15″ 2.2GHz Retina MacBook Pros for $1699 including free shipping plus Apple’s standard one-year warranty. Their price is $300 off MSRP, and... Read more
1.4GHz Mac mini, refurbished, available for $...
The Apple Store has Apple Certified Refurbished 1.4GHz Mac minis available for $419. Apple’s one-year warranty is included, and shipping is free. Their price is $80 off MSRP, and it’s the lowest... Read more
Sale! 15-inch Retina MacBook Pros for up to $...
MacMall has 15″ Retina MacBook Pros on sale for up to $255 off MSRP. Shipping is free: - 15″ 2.2GHz Retina MacBook Pro: $1794.99 save $205 - 15″ 2.5GHz Retina MacBook Pro: $2244.99 save $255 B&H... Read more
Sale! New 11-inch 128GB MacBook Air for $799,...
B&H Photo has the new 2015 11″ 1.6GHz/128GB MacBook Air on sale for $799.99 including free shipping plus NY tax only. That’s $100 off MSRP. Read more

Jobs Board

Hardware Systems Integration Engineer - *App...
Changing the world is all in a day039s work at Apple . If you love innovation, here039s your chance to make a career of it. You039ll work hard. But the job comes with Read more
Senior Identity Architect - *Apple* Pay - A...
Changing the world is all in a day039s work at Apple . If you love innovation, here039s your chance to make a career of it. You039ll work hard. But the job comes with Read more
Hardware Systems Integration Engineer - *App...
Changing the world is all in a day039s work at Apple . If you love innovation, here039s your chance to make a career of it. You039ll work hard. But the job comes with Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** The ASC is an Apple employee who serves as the Apple business manager and influencer in a hyper-business critical Reseller's store which delivers Read more
Technical Project Manager - *Apple* Pay - A...
**Job Summary** Apple Pay is seeking an experienced technical PM…manage the rollout of features to merchants for the Apple Pay platform in the US Within this role Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.