Recursion is a handy trick of logic which involves a method sending a message to itself. It is quite possible to write a method in Objective-C which takes as input the same kind of object as it returns. Have this method call itself and you create a loop within your running program.
I had a problem recently which was solved using a recursive method, which would have been quite difficult to program otherwise.
What I was after was seemingly very simple. I wanted a text field which would show ranges of numbers, neatly grouped and presented. For example, the page range field in Adobe InDesign's or Word's print dialog does something very similar. 1, 2, 3, 5, 6, 7 becomes 1-3, 5-7.
What I needed was a method which would take the NSMutableSet from an Array Controller in Interface Builder, and produce a nice string for my gui. I knew that much, and based on that it seemed reasonable to start with an NSValueTransformer subclass. So far so good. I dubbed it CLSectionPageRangeTransformer.
Now an NSMutableSet is a jumble: like an NSDictionary, it has no inherent order to it. So I knew that I needed to order the output as part of the process as well. For a while I played around with NSMutableArrays, but it just didn't produce the right output, no matter what I seemed to do. And the code got very long and unwieldy in it's brokenness. Always a bad sign.
Eventually in my reading, I came across the idea of a recursive function, that is a function that calls itself, and a light switched on in my head. I wondered if I could apply this technique to my problem. I started coding and to my pleasure I found that I could indeed use this interesting technique to solve my conundrum.
Recursion allows a programmer to easily traverse a tree of unknown length, which is why it is so helpful here. Without recursion, I was forced to write a nested series of iterations which left edge cases which I couldn't handle in my real world problem in a reasonable time.
It turns out that recursion is commonly used in sort functions, which is essentially what I am trying to write. Recursive solutions often tend to be shorter and simpler than non-recursive ones.
I'm not sure if this is the case with my code, which could probably be tidied up. For god's sake don't let Shipley see it!
Recursive algorithms need a few essential features to be useful:
What I came up with is an end recursion. That is, it has a test at the end of the function: if the condition is met, the loop exits. Or else it feeds the results of the current run through back into itself for another loop.
In this case, the value provided by Cocoa Bindings is an NSMutableSet, so my method needs to output an NSMutableSet. So some other method will be needed to handle conversion to a pretty string.
In order to make sure the loop runs the right number of times, we ask for a counter set to the count of items in the NSMutableSet. We count down until the counter reaches zero. This is the test, and when there are no more numbers to process, we are done.
In between, we create and build subsets from the original numbers, removing items from the original set as they are placed in the ordered subsets.
/* recursivePartition: count: takes a set of numbers and recursively returns a set of subsets until all the numbers are in subsets, removing the numbers from the original set as it goes. Counter keeps track of our recursion so we don't get stuck in an infinite loop. It must be set to an initial value of [integers count]. Subsets are built up based on whether numbers are adjacent to other integers in any existing subsets. Essentially we make contiguous ranges out of an unordered collection of integers. */ - (NSMutableSet *) recursivePartition:(NSMutableSet *)integers count:(int)counter { NSMutableSet * subSet; int i = 0; //NSLog(@"Creating recursivePartition instance: \n Count: %d \n With numbers: %@ \n To output: %@ ", counter, integers, output); while (i <= (counter-1)) { //Compare all integers NSEnumerator * numberEnumerator = [[[integers allObjects] sortedArrayUsingSelector:@selector(compare:)] objectEnumerator]; //sort the integers first id numberObject; while (numberObject = [numberEnumerator nextObject])
{ if (i == 0) { //This is the first time through //We need a new subSet subSet = [[[NSMutableSet alloc]init]autorelease]; [subSet addObject:numberObject]; [integers removeObject:numberObject]; [output addObject:subSet]; else { //Compare the integers with the existing output set NSEnumerator * subSetEnumerator = [output objectEnumerator]; id subSetObject; while (subSetObject = [subSetEnumerator nextObject]) { //Within its sorted subSets NSEnumerator * pageEnumerator = [[[subSetObject allObjects] sortedArrayUsingSelector: @selector(compare:)] objectEnumerator]; NSNumber * pageObject; while (pageObject = [pageEnumerator nextObject]) { //Make the comparison unsigned int difference = ([pageObject intValue] - [numberObject intValue]); if (difference == 1 || difference == -1) { //Add the number to the output set [subSetObject addObject:numberObject]; //And remove it so it doesn't count again [integers removeObject:numberObject]; i++; //iterate to keep track of this loop if (counter == 0) { //We've reached the end of the integers return output; else { //We have leftover integers and need to go again output = [self recursivePartition:integers count:[integers count]]; // **** tail recursive call - calls this method again return nil;
This is elementary stuff for computer science graduates, I know. However for me, the discovery of the utility, beauty and simplicity of this little trick of logic made my day.
Some time after I wrote this article, I cleaned it up and simplified it. The new article can be found here.