Saturday, July 12, 2008

Learn Recursion

Todays message is short and sweet.

I was just reading chapter seven of Beautiful Code, "Beautiful Testing". As the chapter begins, the reader is challenged to attempt writing a binary search. Here's mine.
int search(int[] arr, int target) {
return arr.length == 0 ? -1 : search(arr, target, 0, arr.length-1);
}

int search(int[] arr, int target, int min, int max) {
if (min >= max) return target == arr[min] ? min : -1;
int middle = (max + min) >>> 1;
if (arr[middle] > target) return search(arr, target, min, middle-1);
if (arr[middle] < target) return search(arr, target, middle+1, max);
return middle;
}
Yes, it's in Java. I'm not going to rewrite it in eight other languages because that's not the point, for once.

Here's the point: If you call yourself a programmer and don't grok this recursion business, fix it. Now.

This has been a public service announcement brought to you by the "People Who Will Not Take You Seriously If You Don't Understand Recursion" Foundation.

3 comments:

Steve Asher said...

What do you think of the book?

Ray Myers said...

Steve: It has it's ups and downs. Each chapter has a different author, and there are 33 chapters. I wouldn't say every single one of them is stellar, but there are more than enough gems to make the book worth having.

For instance, in Chapter 1, Brian Kernighan discusses Rob Pike's 30-line regular expression matcher, remarking: "It's one of the best examples of recursion that I have ever seen."

Michael Finney said...

Thanks for the comment about the book.

FYI
ISBN # of "Beautiful Code..." book is 0596510047