First Programming Example - Practices

As promised, this one is going to be easy. We will take a well known problem, and see how we can solve it recursively. The problem is searching an array. You are given an array, and you want to search for a certain value inside the array. The non-recursive approach to this problem would be to iterate through the array looking for the value we search for. When it is found, we stop and report success, and if not, we report failure.

Now, let's think recursively. We want to reduce the problem of searching an array into a problem of…well…searching an array. After all, this is how recursion works.

Think of this approach. To search an array whose length is n for the value of v, do the following.

If the element is in the very last position, report as success

If not, search the whole array (except for the last position), for the element we are looking for.

You see, we actually managed to reduce the problem from searching an array into searching an array. Are we forgetting anything? Of course we are: the stopping condition! When should this stop? Luckily this is simple--when you are faced with an empty array, report failure.

Now look at the code to actually implement this…

class List
{
 int[] data=new int[100];
 public boolean search(int v, int n)
 {//v is the value we search for, n is length of array to search
  if(n==0) return false;
  if(data[n-1]==v) return true;
  return search(v,n-1);
 }
}

Take a closer look at this code. I have removed everything, except for the relevant parts. Did you notice that there aren't any loops at all? That's right, we made a search over all the elements of the array without having any kind of loops in the code. Just a couple of if statements, and a return statement! How does it work?

It is a little tricky. First you call search(v,100). This function checks the last element of the array, and if that's the one we want, it returns true. If not, it calls search(v,99). The newly called function checks the position before the last one, and if the element is not found there it calls search(v,98), and so on. If the element is not in the array, the function search() will keep calling itself till it reaches search(v,0), which will return false. If the element is found, the function that finds it will return true.

If you think this is complicated, don’t worry. Recursion looks complicated the first time you see it. I mentioned that recursion is quite counter-intuitive. The human brain can never solve problems recursively. Our brains can only solve problems by thinking of the steps necessary, and doing them one by one. Only computers are comfortable with recursion. Anyway, let's get back to our discussion.

I can hear the skeptics complaining, "I can't see any benefits from using recursion. We solved a simple problem by writing a really tricky piece of code. We could have just lived with a small loop to do the search, and ignore recursion completely." Patience people; I can't say everything at the same time! Let's head into our second example.