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

Notion 2.1.3 - A unified workspace for m...
Notion is the unified workspace for modern teams. Features: Integration with Slack Documents Wikis Tasks More improvements to editing Browse through a page’s images from one place Choose a type... Read more
Cocktail 15.3.7 - General maintenance an...
Cocktail is a general purpose utility for macOS that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
Dropbox 158.4.4564 - Cloud backup and sy...
Dropbox is a file hosting service that provides cloud storage, file synchronization, personal cloud, and client software. It is a modern workspace that allows you to get to all of your files, manage... Read more
WhatsApp 2.2236.10 - Desktop client for...
WhatsApp is the desktop client for WhatsApp Messenger, a cross-platform mobile messaging app which allows you to exchange messages without having to pay for SMS. WhatsApp Messenger is available for... Read more
VOX 3.5.2 - Music player that supports m...
VOX just sounds better! The beauty is in its simplicity, yet behind the minimal exterior lies a powerful music player with a ton of features and support for all audio formats you should ever need.... Read more
TeamViewer 15.34.4 - Establish remote co...
TeamViewer gives you remote control of any computer or Mac over the Internet within seconds, or can be used for online meetings. Find out why more than 200 million users trust TeamViewer! Free for... Read more
ClamXAV 3.5 - Virus checker based on Cla...
ClamXAV is a popular virus checker for OS X. Time to take control ClamXAV keeps threats at bay and puts you firmly in charge of your Mac’s security. Scan a specific file or your entire hard drive.... Read more
Ableton Live 11.2 - Record music using d...
Ableton Live lets you create and record music on your Mac. Use digital instruments, pre-recorded sounds, and sampled loops to arrange, produce, and perform your music like never before. Ableton Live... Read more
Viber 18.5.0 - Send messages and make fr...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device, so... Read more
CrossOver 22.0.1 - Run Windows apps on y...
CrossOver can get your Windows productivity applications and PC games up and running on your Mac quickly and easily. CrossOver runs the Windows software that you need on Mac at home, in the office,... Read more

Latest Forum Discussions

See All

TouchArcade Game of the Week: ‘Tallowmer...
With its pre-determined launch date of September 30th it didn’t quite make it in time for our weekly round-up of new game releases, but darn it, I just don’t care. I’m not letting that technicality keep me from picking Tallowmere 2 as our Game of... | Read more »
SwitchArcade Round-Up: Reviews Featuring...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for September 30th, 2022. In today’s article, our pal Mikhail has another review for us. Gosh, that guy needs a day off! He’s taking a look at Let’s Build a Zoo, and it’s not exactly the... | Read more »
Seven Knights 2 recieves global update i...
Netmarble has announced the latest global update for mobile role-playing game Seven Knights 2. The update will bring brand new characters, some very rewarding events, and reworks to a few old favourite heroes. [Read more] | Read more »
‘GRIS+’ Is This Week’s New Apple Arcade...
Nomada Studio and Devolver Digital’s brilliant GRIS+ () has joined Apple Arcade today as an App Store Great. If you’ve not played it yet, GRIS debuted on PC and Nintendo Switch before seeing PS4 and mobile releases later on. I reviewed the iOS... | Read more »
SwitchArcade Round-Up: Reviews Featuring...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for September 29th, 2022. In today’s article, we have a bunch of new releases to check out with the spearhead being The Elder Scrolls V: Skyrim Anniversary Edition. There’s a little here... | Read more »
‘Residual’ Controller Fix Update Release...
A few weeks back developer OrangePixel released their newest game on mobile called Residual. This is a roguelike survival game where you play as a pilot who crash lands on a procedurally generated planet, filled with all sorts of crazy creatures and... | Read more »
‘Queen’s Wish 2: The Tormentor’ Launchin...
We learned back in July that Spiderweb Software’s latest game Queen’s Wish 2: The Tormentor would be heading to desktop platforms in August, which is exactly what happened, and at that time we were guessing that the iOS version of the game would... | Read more »
‘Kingdom Rush Vengeance’ Primal Ravage U...
Ironhide Game Studio’s Kingdom Rush Vengeance ($4.99) has gotten quite a few updates over the years on iOS, Android, and PC. | Read more »
Interactive Film The Gallery screens at...
The FMV/interactive film hybrid video game genre has been around for a while but doesn’t seem to have that many games out there, but they just might get some more exposure as The Gallery has landed a spot in the Dinar Film Festival 2022. [Read... | Read more »
Terraria’s Massive Labor of Love Update...
Re-Logic’s action platforming sandbox game Terraria ($4.99) has just been updated on mobile and console platforms with its newest major update titled the ‘Labor of Love’ update. | Read more »

Price Scanner via MacPrices.net

Apple has M1 Mac minis in stock again startin...
Apple has restocked a full line of M1-powered Mac minis available in their Certified Refurbished section starting at only $589 and up to $140 off MSRP. Each mini comes with Apple’s one-year warranty... Read more
13″ M1 MacBook Airs with 16GB of RAM availabl...
Apple has 13″ M1 MacBook Airs (8-Core CPU/7-Core GPU) in stock today with 16GB of RAM for $190 off MSRP, Certified Refurbished. Apple includes a standard one-year warranty with these models, each... Read more
Update: 13-inch Apple M2 MacBook Airs now on...
Amazon has 13″ MacBook Airs with M2 CPUs in stock today and on sale for $150 off MSRP. Shipping is free. Their prices are now $150 off Apple’s MSRP, and they are the lowest prices available for these... Read more
Save $240 on a 14″ 8-core CPU M1 Pro MacBook...
Apple has the 14″ M1 Pro MacBook Pro with 32GB of RAM and a 512GB SSD (Space Gray) in stock for $2159, Certified Refurbished. Regular price for this configuration is $2399, so their savings amounts... Read more
Save $170 on this 13″ M2 MacBook Pro with 16G...
Apple has 13″ M2 MacBook Pros with 16GB of RAM and 512GB SSDs in stock today for $170 off MSRP ($1529), Certified Refurbished. These are the cheapest 13″ M2 MacBook Pros with this configuration... Read more
This Apple retailer is offering a $350 discou...
Apple retailer Expercom is offering a $350 instant discount on select upgraded 16″ Apple MacBook Pros through October 4, 2022. Shipping is free. Their sale price applies to the following... Read more
Clearance 27″ 5K Apple iMacs are on sale star...
Other World Computing has dropped prices on Apple refurbished, factory-sealed, recently-discontinued 27″ 5K iMacs with models now on sale for up to $950 off Apple’s MSRP, starting at only $849. Their... Read more
Get a new Mac for up to $400 off MSRP at Appl...
Need a new Apple Mac for school? Whether you’re a student, teacher, or staff member, you can use your .edu email address when ordering at Apple Education to take up to $400 off the price of a new Mac... Read more
13-inch Apple MacBook Airs with M2 processors...
Amazon has 13″ MacBook Airs with M2 CPUs in stock today and on sale for $1099. Shipping is free. Their prices are $100 off Apple’s MSRP, and they are the lowest prices available for M2-powered Macs... Read more
AR Glasses That Work With Apple’s Hardware? T...
NEWS – Lenovo has created quite the spectacle(s) with its latest product. “Apple Glass” — the purported name of Apple’s forthcoming AR glasses — is not expected to be released until 2025 (at the... Read more

Jobs Board

*Apple* Electronic Repair Technician - PlanI...
…a highly motivated individual to join our Production Department as an Apple Electronic Repair Technician. The computer repair technician will diagnose, assemble, Read more
( *Apple* ) Production Designer/Artist - TEKs...
…Art Ops team supports production, asset management, quality control, and global publishing for Apple Media Products, like Apple Music. The Art Ops team is Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall Read more
Sephora Beauty Advisor - *Apple* Blossom Ma...
Sephora Beauty Advisor - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.