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.

 
AAPL
$117.60
Apple Inc.
-1.03
MSFT
$47.47
Microsoft Corpora
-0.12
GOOG
$541.08
Google Inc.
+1.81

MacTech Search:
Community Search:

Software Updates via MacUpdate

MacUpdate Desktop 6.0.3 - Discover and i...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more
SteerMouse 4.2.2 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. It also supports Apple Mighty Mouse very well. SteerMouse can assign various functions to buttons that Apple's software does not allow,... Read more
iMazing 1.1 - Complete iOS device manage...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more
PopChar X 7.0 - Floating window shows av...
PopChar X helps you get the most out of your font collection. With its crystal-clear interface, PopChar X provides a frustration-free way to access any font's special characters. Expanded... Read more
Carbon Copy Cloner 4.0.3 - Easy-to-use b...
Carbon Copy Cloner backups are better than ordinary backups. Suppose the unthinkable happens while you're under deadline to finish a project: your Mac is unresponsive and all you hear is an ominous,... Read more
ForeverSave 2.1.3 - Universal auto-save...
ForeverSave auto-saves all documents you're working on while simultaneously doing backup versioning in the background. Lost data can be quickly restored at any time. Losing data, caused by... Read more
Voila 3.8.1 - Capture, annotate, organiz...
Voila is a screen-capture, recording, and annotation tool that is a full-featured replacement for Mac's screen-capture and screen-recording capabilities. It has a large and robust set of editing,... Read more
SyncTwoFolders 2.0.6 - Syncs two user-sp...
SyncTwoFolders simply synchronizes two folders. It supports synchronization across mounted network drives and it is a possibility to run a simulation showing in a log what will be done. Please visit... Read more
Duplicate Annihilator 5.1.1 - Find and d...
Duplicate Annihilator takes on the time-consuming task of comparing the images in your iPhoto library using effective algorithms to make sure that no duplicate escapes. Duplicate Annihilator detects... Read more
HandBrake 0.10.0 - Versatile video encod...
HandBrake is a tool for converting video from nearly any format to a selection of modern, widely supported codecs. Supported Sources: VIDEO_TS folder, DVD image or real DVD (unencrypted -- CSS is... Read more

Latest Forum Discussions

See All

Screeny (Utilities)
Screeny 1.0 Device: iOS iPhone Category: Utilities Price: $.99, Version: 1.0 (iTunes) Description: Screeny is an utility app that helps you save space consumed by screenshots. It screens your camera roll and helps you to filter and... | Read more »
Tilt to Live Bundle Set to Arrive This T...
Tilt to Live Bundle Set to Arrive This Thanksgiving Posted by Ellis Spice on November 25th, 2014 [ permalink ] One Man Left has unveiled an upcoming Tilt to Live bundle, allowing players to get the series for a di | Read more »
BattleLore: Command (Entertainment)
BattleLore: Command 1.0 Device: iOS Universal Category: Entertainment Price: $9.99, Version: 1.0 (iTunes) Description: ***NOTE: Compatible with iPad 2/iPad mini, iPod touch 5 and up and iPhone 4S and up – WILL NOT RUN ON EARLIER... | Read more »
Weather Or Not Review
Weather Or Not Review By Jennifer Allen on November 25th, 2014 Our Rating: :: STYLISH WEATHER REPORTINGiPhone App - Designed for the iPhone, compatible with the iPad Check the weather quickly and conveniently with Weather or Not... | Read more »
The All-New Football Manager Handheld 20...
The All-New Football Manager Handheld 2015 is Available Now Posted by Jessica Fisher on November 25th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Six iOS Games to Get You Ready for Thank...
Image Source: Friends Wiki At this point in the month, you or at least a few people you know are probably getting ready to scramble around (or are already scrambling around) for Thanksgiving Dinner. It’s a hectic day of precise oven utilization, but... | Read more »
Call of Duty: Heroes: Tips, Tricks, and...
Hello Heroes: What’d we think of Call of Duty‘s take on Clash of Clans? Check out our Call of Duty: Heroes review to find out! Just downloaded Call of Duty: Heroes and need some handy tips and tricks on how to get ahead of the rest? As we often do,... | Read more »
Call of Duty: Heroes Review
Call of Duty: Heroes Review By Jennifer Allen on November 25th, 2014 Our Rating: :: CLASH OF FRANCHISESUniversal App - Designed for iPhone and iPad Mix Clash of Clans with Call of Duty, and this is what you get.   | Read more »
Slider Review
Slider Review By Jordan Minor on November 25th, 2014 Our Rating: :: SLIDE TO PLAYUniversal App - Designed for iPhone and iPad Slider has all the excitement of unlocking your phone screen.   | Read more »
oh my giraffe (Games)
oh my giraffe 1.0.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.0 (iTunes) Description: Eat fruits while being chased by lions. Cut the vines to send fruit plummeting onto the lions. Don't worry, your flexible... | Read more »

Price Scanner via MacPrices.net

Early Black Friday MacBook Pro sale: 15-inch...
 Best Buy has posted early Black Friday prices on 15″ Retina MacBook Pros, with models on sale for $300 off MSRP on their online store for a limited time. Choose free local store pickup (if available... Read more
A9 Chips Already?
It’s barely more than a couple of months since Apple got the first A8 systems-on-chip into consumer hands, but rumor and news focus is already turning to the next-generation A9 SoC. Apple Daily... Read more
NewerTech Announces NuGuard KXs Impact X-Orbi...
NewerTech has announced updates to its family of Impact X-Orbing Screen Armor bringing military grade, triple layer protection to Apple’s new iPhone 6 and 6 Plus. Like all models in the NuGuard KXs... Read more
13-inch 1.4GHz MacBook Air on sale for $889,...
 B&H Photo has the 13″ 1.4GHz/128GB MacBook Air on sale for $889 including free shipping plus NY tax only. Their price is $110 off MSRP. B&H will also include free copies of Parallels Desktop... Read more
Save up to $300 on Macs and iPads with your A...
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 Mac Pros available for up t...
The Apple Store is offering Apple Certified Refurbished Mac Pros for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Jumptuit Launches One-Tap Windows 8.1 iTunes...
Jumptuit has launched Windows 8.1 support for One-Tap iTunes Sync. with which Windows 8.1 users can now easily sync their iTunes libraries with Microsoft OneDrive. Jumptuit provides easy access from... Read more
Apple restocks refurbished 13-inch 2014 Retin...
The Apple Store has restocked Apple Certified Refurbished 2014 13″ 2.6GHz Retina MacBook Pros for up to $230 off the cost of new models. An Apple one-year warranty is included with each model, and... Read more
CEA Study Finds More People Recycling Electro...
A new study by the Consumer Electronics Association (CEA) finds that electronics recycling receives the continued and growing support of consumers. According to the CEA,s Recycling and Reuse Study,... Read more
15″ 2.2GHz Retina MacBook Pro on sale for $17...
 B&H Photo has the 2014 15″ 2.2GHz Retina MacBook Pro on sale today for $1749. Shipping is free, and B&H charges NY sales tax only. B&H will also include free copies of Parallels Desktop... Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**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
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Retail - Multiple Positions (US) - A...
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
*Apple* Solutions Consultant (ASC) - Apple (...
**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
*Apple* Solutions Consultant (ASC) - Apple (...
**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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.