Beginning Recursion

Since I consider recursion to be one of my weaker areas, I'm going to start off by improving this particular  aspect of my programming skills.To be honest, recursion is probably the area that I'm most uncomfortable with, so what better way to start off my development program?!

I just picked up a good book on algorithms from the library - "Algorithms" (Johnsonbaugh & Schaefer, 2004). Well, it has two 4-star reviews on Amazon, with reasonably reliable comments. The book does not have a specialized section dedicated to recursion. It comes up as part of divide-and-conquer algorithms and also in the introductory section on recurrence relations, but I am looking for a fundamental, self-contained section just on the recursive programming concept. I shall get back to the book a bit later to master the divide and conquer technique, once I'm completely comfortable with the basics of recursion.

Online, I found a tutorial on recursive programming: http://erwnerve.tripod.com/prog/recursion/recintro.htm. It has an interesting analogy/imagination technique that can be used to visualize and better understand recursion. The page also has a few good exercises that should help me improve.

First exercise is Factorial calculation. I remember I programmed this sometime before, as Java does not have an in-built Math function to do this. It is important to remember to have the base condition (aka end condition), so the recursive calling stops in the end and returns the (final) answer. My code is as follows:

      private int factorial(int n){  
           if(n == 1)  
                return 1;  
           else  
                return factorial(n-1) * n;  
      }  

I ran some tests on random integers: 3, 10, 20, 50. 3 and 10 return correct results (checked against Windows calculator), but 20 returns a negative number and 50 returns 0. The answers for these numbers will be out of range for the "int" data type, so I suppose it's reasonable to expect wrong results - to be honest, I was expecting some kind of "out of range" exception to be thrown by Java.

Checking the solution with the one on the web page, the code is identical (except for the order of operands). Now let's do the exercises on the bottom of the page.

Printing Number Sequences
First exercise is to "Write a function using Recursion to print numbers from n to 0". This is my code:

      private void printSequence(int n){  
           if(n == 0)  
                System.out.print(n);  
           else{  
                System.out.print(n + " ");  
                printSequence(n - 1);  
           }  
      }  

Of course, the obvious solution to this problem would be to use a for loop, but it's an interesting practice for recursion nonetheless...

The next problem is to "Write a function using Recursion to print numbers from 0 to n". This appears to be much less trivial than the previous exercise, mainly because we have to keep track of the current depth, as well as the end condition - with only one function argument. Or so it seems... It turns out that we must use the "function return waiting" feature of recursion:

      private void printSequenceReverse(int n){  
           if(n == 0)  
                System.out.print(0 + " ");  
           else{  
                printSequenceReverse(n - 1);  
                System.out.print(n + " ");  
           }  
      }  

We reverse the order of the previous algorithm, by doing the recursive call first, and only printing the result after the call returns. So the algorithm goes all the way to depth n, prints "0", and print out the function stack value of "n" at each subsequent level.

Reversing a String
Next, the third exercise asks to "Write a function using Recursion to enter and display a string in reverse". It also requests that we don't use arrays/string, so I assume the author expects us to use memory pointers. Since we're using Java, let's just try to solve it using the String class:

      private void reverseString(String s){  
           if(s.length() == 1)  
                System.out.print(s);  
           else{  
                System.out.print(s.charAt(s.length() - 1));  
                reverseString(s.substring(0, s.length() - 1));  
           }  
      }  

This code prints the last character of the string first, then makes a recursive call with the string with last character removed. Finally, when the length reaches one, it means we're only left with the first character of the original string. Perhaps a cleaner version of this code can be written using what we've learned from previous exercise:

      private void reverseString(String s){  
           if(s.length() == 1)  
                System.out.print(s);  
           else{  
                reverseString(s.substring(1));  
                System.out.print(s.charAt(0));  
           }  
      }  

This version goes to the deepest level before printing anything by using the one-argument substring function that takes the substring from the specified beginning index.  So the first character to be printed will be the last character of the original string. This is great that we can apply what we've learned in the most basic examples right away!

Checking for Prime Numbers
Exercise 5 asks us to "Write a function using Recursion to check if a number n is prime". So this means, we just need to check if the given number if divisible by any other number smaller than it. Should be simple enough to implement, with all the experience from previous exercises! Definition of a prime number from wikipedia: "A natural number is called a prime number (or a prime) if it is greater than one and has no divisors other than 1 and itself". Here is my code:

      private boolean checkPrime(int n){  
           if(n > 1)  
                return _checkPrime(n, 2);  
           else  
                return false;  
      }  
      private boolean _checkPrime(int n, int m){  
           if(m == n)  
                return true;  
           else{  
                if(n % m == 0)  
                     return false;  
                else  
                     return _checkPrime(n, m+1);  
           }  
      }  

http://primes.utm.edu/lists/small/1000.txt

Note that there is some redundancy in this code, which would become apparent for very large number. Can you spot it? We actually only need to check divisibility up to the square root of the input - details and more interesting facts can be found here: http://en.wikipedia.org/wiki/Primality_test