Tuesday, October 26, 2004

isPalindrome() as a recursive function

I had my first encounter with recursion in programming was in the spring when I was taking Computer Science 2010. We were programming in a language called Scheme, which as I look back on it now was a great experience. At our meager level, linked-lists were the name of the game, and recursion was the way to get through them. We never got access to the notion of the “for” loop, at least not in that language. We spent time developing functions that would count, sort, and find/replace. At first it was hard for some of us to understand why we were approaching programming that way, but when we started working in Java, we certainly appreciated the beauty of the “while” and “for” loop.

Since all of that work in Scheme, we haven’t spent much time with recursion. Now and again, the professor will make mention of it, and remind us that perhaps it would be a way to approach a given programming problem. We spent some time with recursion in talking about algorithm analysis, but really we haven’t had to program with it much. Once one gets the hang of it, thinking recursively can actually be fun. It does however; depend on the programmer understanding the basics of recursion.

In our last class assignment, one of the questions was to write a recursive function called isPalindrome(). The function needed to be able to accept a string, and determine whether or not it was a palindrome or not. Now, for those of you that don’t know, a palindrome is to quote Webster: A word, phrase, verse, or sentence that reads the same backward or forward. With the formal definition out of the way, an example of a palindrome would be “RACECAR”, another would be “Madam I’m Adam.” The function needs to be able to ignore punctuation, and compare character by character to make sure that they are the same.

In a recursive programming one of the most important steps is to be sure that you know what the base case is. If you don’t know the base case, then your function may run on forever and ever. The base case is something that you give the function so that it knows when to stop.

Depending on how you approach the problem you may be able to find different base cases. For example, the way I created this function, my base case was when the string had been reduced to one, or zero characters. If you were given i and j as integers, representing valid indices for the input string, you could test for i <= j as your stopping point. At any rate, you need some way to be able to stop the function, and the base case is the way to it in recursion.

It was a pretty fun assignment; I enjoyed talking with my classmates about the different ways that they approached it. This page shows two different ways to code isPalindrome() recursively in Java.

Cheers for recursion, and the joy of playing with letters and words!

No comments: