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

Luminar 1.0.2 - Powerful, adaptive, conf...
Luminar is the new full-featured image editor that adapts to the way you edit photos. Over 300 essential tools to fix, edit, and enhance your photos with comfort. The future of photo editing is here... Read more
WhatRoute 2.0.10 - Geographically trace...
WhatRoute is designed to find the names of all the routers an IP packet passes through on its way from your Mac to a destination host. It also measures the round-trip time from your Mac to the router... Read more
Slack 2.3.3 - Collaborative communicatio...
Slack is a collaborative communication app that simplifies real-time messaging, archiving, and search for modern working teams. Version 2.3.3: Fixed window zoom jumping back-and-forth OS X 10.9... Read more
Lens Blur 1.4.3 - True out-of-focus boke...
Lens Blur transforms your existing photo into true SLR-quality out-of-focus bokeh effect! Everyone needs a gorgeous personalized background for a social profile, blog, Web/UI design, presentation, or... Read more
CleanMyMac 3.6.0 - $39.95
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
DEVONthink Pro 2.9.8 - Knowledge base, i...
DEVONthink Pro is your essential assistant for today's world, where almost everything is digital. From shopping receipts to important research papers, your life often fills your hard drive in the... Read more
MacFamilyTree 8.1 - Create and explore y...
MacFamilyTree gives genealogy a facelift: modern, interactive, convenient and fast. Explore your family tree and your family history in a way generations of chroniclers before you would have loved.... Read more
HoudahSpot 4.2.7 - Advanced file-search...
HoudahSpot is a powerful file search tool. Use HoudahSpot to locate hard-to-find files and keep frequently used files within reach. HoudahSpot will immediately feel familiar. It works just the way... Read more
TunnelBear 3.0.7 - Subscription-based pr...
TunnelBear is a subscription-based virtual private network (VPN) service and companion app, enabling you to browse the internet privately and securely. Features Browse privately - Secure your data... Read more
Garmin Express 4.5.0.0 - Manage your Gar...
Garmin Express is your essential tool for managing your Garmin devices. Update maps, golf courses and device software. You can even register your device. Update maps Update software Register your... Read more

Latest Forum Discussions

See All

Amateur Surgeon 4 Guide: Become the worl...
It's time to wield your trusty pizza cutter again, as Amateur Surgeon has returned with a whole fresh set of challenges (and some old, familiar ones, too). Starting anew isn't easy, especially when all you have at your disposal is a lighter, the... | Read more »
Le Parker: Sous Chef Extraordinaire (Ga...
Le Parker: Sous Chef Extraordinaire 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »
Telltale Games really is working on a Gu...
Telltale Games' next episodic adventure is indeed Guardians of the Galaxy. A document tied to the voice actors strike suggested that the project was in the work, but now we have direct confirmation following an announcement at the Game Awards that... | Read more »
Amateur Surgeon returns to iOS and Andro...
Amateur Surgeon and its two sequels disappeared from the App Store some time and it was sad days for all. But now, just in time for the holidays, the Adult Swim favorite makes its joyous return in the shape of Amateur Surgeon 4, a remake with... | Read more »
The best board games on mobile
Sometimes you need to ditch all of the high speed, high action games in favor of something a little more traditional. If you don't feel like parting ways from your mobile device, though, there are still plenty of ways to get that old-school fix.... | Read more »
The best Facebook Messenger Instant Game...
Facebook's new Instant Games is now here, meaning you can play games with your friends directly via Facebook. It's a fun new way to connect with friends, of course, but it's also proving to be a solid gaming experience in its own right, with a... | Read more »
You can now play game's on Facebook...
Facebook launched its new Instant Games platform in an exciting new attempt to engage its user base. As a result, you can now play a number of different games directly through Facebook Messenger. All of these games run with HTML5, meaning you play... | Read more »
Apollo Justice Ace Attorney (Games)
Apollo Justice Ace Attorney 1.00.00 Device: iOS Universal Category: Games Price: $.99, Version: 1.00.00 (iTunes) Description: Court Is Back In Session Star as rookie defense attorney, Apollo Justice, as he visits crime scenes,... | Read more »
KORG iWAVESTATION (Music)
KORG iWAVESTATION 1.0 Device: iOS Universal Category: Music Price: $19.99, Version: 1.0 (iTunes) Description: A revolutionary new world of sound.The Wave Sequence Synthesizer for iPad - KORG iWAVESTATION | Read more »
Don't Grind Guide: Tips for becomin...
Don’t Grind is a surprising, derpy little one touch game with fun hand-drawn graphics. The goal is simple -- get the high score without being chopped to bits. That can be tough when you’re not used to the game, and that’s compounded by the fact... | Read more »

Price Scanner via MacPrices.net

Parallels Toolbox 1.3 for Mac Offers 25 Singl...
Parallels has launched Parallels Toolbox 1.3 for Mac, an upgrade that adds five new utilities to the stand-alone application which was released in August and is available exclusively online at http... Read more
OWC Mercury Elite Pro Dual mini Ultra-Portabl...
OWC has introduced the new OWC Mercury Elite Pro Dual mini, a powerful yet ultra-portable dual-drive RAID solution. The new Mercury Elite Pro Dual mini packs phenomenal performance into a small... Read more
Clearance 13-inch Retina MacBook Pros availab...
B&H Photo has clearance 2015 13″ Retina Apple MacBook Pros available for up to $200 off original MSRP. Shipping is free, and B&H charges NY tax only: - 13″ 2.7GHz/128GB Retina MacBook Pro: $... Read more
Roundup of 2016 13-inch 2.0GHz MacBook Pro sa...
B&H has the non-Touch Bar 13″ MacBook Pros in stock today for $50-$100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.0GHz MacBook Pro Space Gray (MLL42LL/A): $1449 $... Read more
New 13-inch 2.0GHz Space Gray MacBook Pro in...
Adorama has the new 13″ 2.0GHz Space Gray MacBook Pro (non-Touch Bar, MLL42LL/A) in stock for $1499 including a free 3-year AppleCare Protection Plan. Shipping is free, and Adorama charges sales tax... Read more
Finnair Adopts iOS Enterprise iPad Apps from...
Finnair and IBM have announced a first-of-its-kind agreement to utilize iOS enterprise apps from IBM to support the airline’s overall digital transformation. Finnair is focused on Asia-Europe traffic... Read more
Tech21 Launches Evo Go iPhone 7 Case Availabl...
Tech21 has announced the launch of the Evo Go case for Apple iPhone 7 and iPhone 7 Plus, exclusively at T-Mobile. Available online and at participating T-Mobile stores nationwide, Evo Go cases start... Read more
Apple Turns (RED) with More Ways to Join the...
In recognition of World AIDS Day, Apple is offering more ways than ever for customers to join (RED) in its mission to create an AIDS-free generation. Apple is the worlds largest corporate contributor... Read more
Deals on new 15-inch Touch Bar MacBook Pros,...
B&H Photo has new 2016 Apple 15″ Touch Bar MacBook Pro models in stock today with some available for $50 off MSRP, each including free shipping plus NY sales tax only: - 15″ 2.7GHz Touch Bar... Read more
12-inch Retina MacBooks on sale for up to $10...
12-inch Retina MacBooks remain on sale at B&H Photo with models available for up to $100 off MSRP. Shipping is free, and B&H charges NY sales tax only. B&H will also include a free copy... Read more

Jobs Board

*Apple* Retail - Multiple Positions- White P...
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
Automotive Detailer - *Apple* Used Autos -...
We are currently conductinginterviews and will be accepting applications for a part-time detailer. Apple Used Autos is a great place to work andstart a career. We Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
US- *Apple* Store Leader Program - Apple (Un...
…Summary Learn and grow as you explore the art of leadership at the Apple Store. You'll master our retail business inside and out through training, hands-on Read more
*Apple* & PC Desktop Support Technician...
Apple & PC Desktop Support Technician job in Dallas TX Introduction: We have immediate job openings for several Desktop Support Technicians with one of our most Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.