Recursion in Objective-C

Introduction

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:

  • A way to avoid infinite recursion: Infinite recursion is, umm, undesirable. It's an efficient way to spoil your user's experience with your product.
  • To accept as input the same data type as is output. Well this seems obvious, but it presents a challenge in practise.
  • A call to itself. That's why it's recursive! D'oh!

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];
                        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;
 

Conclusion

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.

Update

Some time after I wrote this article, I cleaned it up and simplified it. The new article can be found here.

References

http://www.science.uva.nl/~mes/jargon/t/tailrecursion.html

C-based mini environments

Correct me if I'm wrong (my C is rusty), but if you'd do this:
{
// Some code + variables
}
It'll create an environment that gets disposed of at the closing "}", right?

This way you can do true recursion in C by doing the work within these curly-brackets and only keep return values outside of these. By using these while loops, you already do this.

Submitted by mvcoile on Thu, 02/21/2008 - 00:14.
Tail-Recursion

I believe the term (proper) tail-recursion is used only for languages which clean-up their environment, except for the last (tail) line to optimize the loop/recursion. Like Lisp/Scheme. Correct me if I'm wrong.

Submitted by mvcoile on Wed, 02/20/2008 - 23:58.

Post new comment

The content of this field is kept private and will not be shown publicly.
Enter the code shown in the image:

CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
6 + 14 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.

Donate!





If you like what you find here and wish to support further development of this site, please donate via PayPal. No account required.

Syndicate

Syndicate content

User login

CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
10 + 2 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.
Enter the code shown in the image: