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

Latest Forum Discussions

See All

Soft Drummer (Music)
Soft Drummer 1.0 Device: iOS Universal Category: Music Price: $14.99, Version: 1.0 (iTunes) Description: Soft Drummer is the closest thing to a pro session subtle drummer in your pocket. Easy to use and fast, it's much more than a... | Read more »
Is GO Gear the Pokemon GO map app you...
Now that we've settled into something of a Pokemon GO status quo, the number one desire of most players can best be summed out by modifying a quote from Rod Tidwell of Jerry Maguire: "Show me the Pokemon!" [Read more] | Read more »
Rodeo Stampede update: Mountains, new an...
The Savannah and Jungle were just the beginning in Rodeo Stampede. Get ready to head for the Mountains. I think I heard that in a beer ad once. [Read more] | Read more »
COSMOS RINGS (Games)
COSMOS RINGS 1.0.0 Device: iOS iPhone Category: Games Price: $5.99, Version: 1.0.0 (iTunes) Description: This game cannot be played without the Apple Watch.Released anniversary sale until August 31,2016 PST! A tragic tale of time's... | Read more »
How to get started selling on Mercari
As far as ecommerce has come over the last decade or so, there's still a tremendous opportunity to make it easier for people to buy and sell goods. That's especially true when it comes to shopping apps, which should only continue to increase in... | Read more »
Human Anatomy Atlas 2017 Edition - Compl...
Human Anatomy Atlas 2017 Edition - Complete 3D Human Body 1.0.24 Device: iOS iPhone Category: Medical Price: $24.99, Version: 1.0.24 (iTunes) Description: | Read more »
Heroes of Normandie (Games)
Heroes of Normandie 1.5 Device: iOS Universal Category: Games Price: $14.99, Version: 1.5 (iTunes) Description: The game does not support iPhone 4s and below | Read more »
Why you should never power up Pokemon in...
There's no question that candy is dandy in Pokemon GO. You need big quantities of it to evolve your Pokemon, and when combined with stardust, it can be used to power up your favorite pocket monsters as well, making them more formidable for the gym... | Read more »
Webzen launches 3D MMORPG MU Origin on i...
Mu Origin is featured time and time again at the very top of App Stores in China, and within the top five worldwide top-grossing charts on Google Play.Its popularity in Korea and China, featuring more than 120 registered players in China and 6... | Read more »
Severed (Games)
Severed 1.0 Device: iOS Universal Category: Games Price: $5.99, Version: 1.0 (iTunes) Description: LAUNCH DISCOUNT ON NOW!! ENDS AUGUST 4! ==== Take control of a one-armed warrior named Sasha, wielding a living sword on her journey... | Read more »

Price Scanner via MacPrices.net

Second-Quarter Tablet Shipments Fell 4.8% –...
The latest report from the global market research firm TrendForce finds that worldwide tablet shipments for this second quarter totaled 33.54 million units, representing a quarterly drop of 4.8% and... Read more
Global Smartphone Sales Volumes Mark Second S...
According to preliminary results from the International Data Corporation (IDC) Worldwide Quarterly Mobile Phone Tracker, vendors shipped a total of 343.3 million smartphones worldwide in the second... Read more
Apple TVs on sale for $20-$40 off MSRP
Best Buy has 32GB and 64GB Apple TVs on sale for $20-$40 off MSRP on their online store. Choose free shipping or free local store pickup (if available). Sale prices for online orders only, in-store... Read more
Mac minis on sale for $50-$100 off MSRP
B&H Photo has Mac minis on sale for $50 off MSRP including free shipping plus NY sales tax only: - 1.4GHz Mac mini: $449 $50 off MSRP - 2.6GHz Mac mini: $649 $50 off MSRP - 2.8GHz Mac mini: $949... Read more
Clearance 2015 13-inch MacBook Airs available...
B&H Photo has clearance 2015 13″ MacBook Airs available for $300 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 1.6GHz/4GB/128GB MacBook Air (MJVE2LL/A): $799... Read more
Apple certified refurbished iPad mini 4s avai...
Apple has certified refurbished iPad mini 4s now available for up to $120 off the cost of new models. An Apple one-year warranty is included with each iPad, and shipping is free. The following models... Read more
Notebook Makers In No Rush To Adopt USB-C – R...
Digitimes’ Cage Chao and Joseph Tsai note that while the USB Type-C interface is enjoying growing popularity among smartphones and tablet makers, notebook and all-in-one (AIO) PC vendors (other than... Read more
iMacs on sale for up to $250 off MSRP
B&H Photo has 21″ and 27″ Apple iMacs on sale for up to $250 off MSRP including free shipping plus NY sales tax only: - 27″ 3.3GHz iMac 5K: $2049 $250 off MSRP - 27″ 3.2GHz/1TB Fusion iMac 5K: $... Read more
12-inch 1.1GHz Retina MacBooks on sale for up...
Amazon has 2016 12″ 1.1GHz/256GB Retina MacBooks on sale for up to $100 off MSRP including free shipping: - 12″ 1.1GHz Space Gray Retina MacBook: $1199 $100 off MSRP - 12″ 1.1GHz Silver Retina... Read more
Bare Bones Software Releases Free TextWrangle...
Bare Bones Software has announced the release and immediate availability of TextWrangler 5.5, a significant update to its powerful, free, general purpose text editor for Mac OS X. TextWrangler is a... Read more

Jobs Board

*Apple* Solutions Consultant - APPLE (United...
Job Summary As an Apple Solutions Consultant, you'll be the link between our future customers and our products. You'll showcase your entrepreneurial spirit as you Read more
Lead *Apple* Solutions Consultant - APPLE (...
Job Summary The Lead ASC is an Apple employee who serves as the Apple business manager and influencer across a number of Reseller locations. The Lead ASC's role Read more
*Apple* Retail - Multiple Positions, Charles...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions, Willow...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Evangelist - JAMF Software (United S...
The Apple Evangelist is responsible for building and cultivating strategic relationships with Apple 's small and mid-market business development field teams. This Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.