Recursion in Objective-C


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.

The Problem

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.

Recursive functions

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!

The Rules of Recursion

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:

   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];
			{	//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;
	{	//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.