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

FileZilla 3.51.0 - Fast and reliable FTP...
FileZilla (ported from Windows) is a fast and reliable FTP client and server with lots of useful features and an intuitive interface. Version 3.51.0: Bugfixes and minor changes: Fixed import of... Read more
KeyCue 9.8 - Displays all menu shortcut...
KeyCue has always been a handy tool for learning and remembering keyboard shortcuts. With a simple keystroke or click, KeyCue displays a table with all available keyboard shortcuts, system-wide... Read more
AppCleaner 3.5.1 - Uninstall your apps e...
AppCleaner allows you to uninstall your apps easily. It searches the files created by the applications and you can delete them quickly. Version 3.5.1: Fixed a code-signing issue causing AppCleaner... Read more
A Better Finder Attributes 7.03 - Change...
A Better Finder Attributes allows you to change JPEG & RAW shooting dates, JPEG EXIF meta-data tags, file creation & modification dates, file flags and deal with invisible files. Correct EXIF... Read more
Postbox 7.0.33 - Powerful and flexible e...
Postbox is a desktop feature-stuffed email client, news application, and feed reader that helps you manage your work life and increase productivity. Now you can organize all your email accounts in... Read more
Adobe InCopy 16.0 - Create streamlined e...
InCopy is available as part of Adobe Creative Cloud for $52.99/month (or $4.99/month for InCopy app only). Adobe InCopy, ideal for large team projects involving both written copy and design work,... Read more
Steam 2.0 - Multiplayer and communicatio...
Steam is a digital distribution, digital rights management, multiplayer and communications platform developed by Valve Corporation. It is used to distribute a large number of games and related media... Read more
Adobe Lightroom Classic 10.0 - Import, d...
You can download Lightroom for Mac as a part of Creative Cloud for only $9.99/month with Photoshop, included as part of the photography package. The latest version of Lightroom gives you all of the... Read more
Adobe InDesign 16.0 - Professional print...
InDesign is available as part of Adobe Creative Cloud for as little as $20.99/month (or $9.99/month if you're a previous InDesign customer). Adobe InDesign is part of Creative Cloud. That means you... Read more
Adobe After Effects 17.5 - Create profes...
After Effects is available as part of Adobe Creative Cloud for $52.99/month (or $20.99/month for a single app license). The new, more connected After Effects can make the impossible possible. Get... Read more

Latest Forum Discussions

See All

Genshin Impact Currency Guide - What...
Genshin Impact is great fun, but make no mistake: this is a gacha game. It is designed specifically to suck away time and money from you, and one of the ways the game does this is by offering a drip-feed of currencies you will feel compelled to... | Read more »
XCOM 2 Collection on iOS now available f...
The XCOM 2 Collection, which was recently announced to be coming to iOS in November, is now available to pre-order on the App Store. [Read more] | Read more »
Presidents Run has returned for the 2020...
IKIN's popular endless runner Presidents Run has returned to iOS and Android just in time for the 2020 election season. It will see players choosing their favourite candidate and guiding them on a literal run for presidency to gather as many votes... | Read more »
New update for Cookies Must Die adds new...
A new update for Rebel Twins’ platformer shooter Cookies Must Die is coming out this week. The update adds quite a bit to the game, including new levels and characters to play around with. [Read more] | Read more »
Genshin Impact Guide - How to Beat Pyro...
The end game of Genshin Impact largely revolves around spending resin to take on world bosses and clear domain challenges. These fights grant amazing rewards like rare artifacts and ascension materials for weapons and adventurers, but obviously... | Read more »
Moto Rider GO has received a huge update...
Moto Rider GO: Highway Traffic is a popular free-to-play racing game that initially launched back in 2017 and has since racked up over 100 million downloads. Today it has received a sizeable update that introduces several KTM and Husqvarna... | Read more »
ORDESA is a spooky interactive film that...
French studio Cinétévé Experience and ARTE have released interactive movie ORDESA for iOS and Android today. It arrives at the perfect time of year, telling a story about a mysterious haunted house that the viewer suddenly finds themselves lost in... | Read more »
Genshin Impact Guide - How to Beat Storm...
If you've followed our progression guide for Genshin Impact up to Adventure Rank 25, you have reached the point where you can face off against Stormterror on a weekly basis for some pretty sweet rewards. Beating this deadly dragon isn't as easy as... | Read more »
MU Origin 2’s new update welcomes back l...
MU Origin 2 developer Webzen continues to churn out new content for the popular MMORPG and, true to form, it’s just released another update. This one encourages lapsed players to return to the game with the promise of new quests and rewards. [... | Read more »
Genshin Impact Guide - Everything you ne...
Genshin Impact has unveiled its first of what we can expect to be many special events and ongoing content updates. This latest update adds the Elemental Crucible Event. This event is available to any players that have reached Adventure Rank 20,... | Read more »

Price Scanner via MacPrices.net

Apple has 2020 13″ MacBook Airs available sta...
Apple has a full line of Certified Refurbished 2020 13″ MacBook Airs available starting at only $849 and up to $200 off the cost of new Airs. Each MacBook features a new outer case, comes with a... Read more
These major wireless carriers will give you a...
Apple’s wireless partners are offering several deals on iPhone 12 pre-orders right now. If you’re willing to switch carriers, you can get a free iPhone 12 right now. Here’s where to take advantage of... Read more
4 day sale at Sams Club: Save $24-$29 on Appl...
Sams Club has Apple Watch Series 6 GPS models on sale this week for $24-$29 off Apple’s MSRP, starting at $374. Sale ends this Thursday, October 22nd: – 40mm Apple Watch Series 6 GPS: $374.98, save $... Read more
US Cellular offers Apple iPhone 12 Pro for $8...
US Cellular has the 2020 128GB iPhone 12 Pro available for $829 off MSRP for new customers signing up for an Unlimited data plan, or $5.66 per month. Cost of the phone is spread over a 30 month... Read more
Buy one Apple Watch SE or Series 6 at AT&...
Buy one Apple Watch SE or Series 6 at AT&T, and get $200 off the price of a second Apple Watch. One new line required, and price discounted reflected in bill credits over a 30 month period. The... Read more
AT&T offers free iPhone 12, $800 off iPho...
AT&T is offering Apple’s new iPhone 12 for free, or up to $800 off the iPhone 12 Pro, for customers opening a new line of service plus an eligible trade-in. Discount is applied via monthly bill... Read more
US Cellular offers free iPhone 12 for custome...
US Cellular has the 2020 64GB iPhone 12 available for free for new customers signing up for an Unlimited data plan. Cost of the phone is spread over a 30 month period. The fine print: “Promotional... Read more
New Xfinity Mobile promo: Take $250 off Apple...
New customers opening a new line of service can take $250 off the purchase of Apple’s new iPhone 12 or iPhone 23 Pro at Xfinity Mobile through 1/4/21. Service plan required. Their offer reduces the... Read more
New at Verizon: Get the Apple 2020 64GB iPhon...
Verizon is offering the new 2020 64GB iPhone 12 for free for customers switching and opening a new line of service, pre-orders starting at October 16, 2020. They’re offering up to $800 off on 128GB... Read more
Verizon offers the new iPhone 12 Pro for $800...
Verizon is offering the new 2020 iPhone 12 Pro for $800 off MSRP for pre-orders, starting on October 16, 2020. Their offer reduces the price of the 128GB iPhone 12 Pro, for example, to only $199.99... Read more

Jobs Board

Department Manager- Tech Shop/ *Apple* Stor...
…their parents want, and our faculty needs. As a Department Manager in our Tech Shop/ Apple Store you will spend the majority of your time on the sales floor engaging Read more
Geek Squad *Apple* Consultation Professiona...
**782284BR** **Job Title:** Geek Squad Apple Consultation Professional **Job Category:** Store Associates **Store Number or Department:** 000140-San Carlos-Store Read more
*Apple* /Mac IT Support - Randstad (United St...
Apple /Mac IT Support **job details:** + location:San Francisco, CA + salary:$45 - $50 per hour + date posted:Thursday, October 8, 2020 + job type:Contract + Read more
Partner Champion, *Apple* - Insight Network...
Partner Champion, Apple Tempe, AZ, US Requisition Number:78333 As an Apple Partner Champion at Insight, you represent and manage gross profit goals for a valued Read more
Platform - Workplace Eng - *Apple* Enterpri...
MORE ABOUT THIS JOB We are looking for an Apple Platform Engineer who will bring a unique engineering skill set, support, clarity, organization and above all else, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.