Recursion Examples
  originally by Nicholas Ruozzi and Lisa Minich (2005)
  enhanced/fixed by Andrew Tibbits, Changxi Zheng, David Schwartz (2006)

Here's a mathematical view of Recursion:

We want to take the kth state and reduce it to the (k-1)th state. 
When does k stop? The "base case" (i.e., stopping point) of a recursive 
problem. 

A problem that involves a repeated solution can be thought of
as iterative:

  example) iterative sum of numbers 0 through k:

  int sum =0;
  for(int i=1; i<=k; i++) { // stop when max # reached
     sum += i;          // increment sum
  }

or recursive:

  example) recursive sum of numbers

  public int sum(int n) {
     if(n==0) // base case
        return 0;
     else // recursive case
        return sum(n-1) + n; 
  }

  The nth state is added to the (n-1) th state for all n greater
  than the base case, which is 0 in this example.

When should you use iteration or recursion?

 - Development process: which is clearer? more intuitive?
   (often recursion)
 - Runtime performance: which involves less memory? faster processing?
   (often iteration)

These questions will be easier to address as you learn more about data
structures and algorithm analysis.

Tail Recursion:

A method is tail recursive if the last action of the recursive method
is the recursive call. In the examples below, the solutions to Problems 
1 and 2 are not tail recursive, but the solution to Problem 3 is tail
recursive. Because recursion builds frame upon frame of the stack, the
additional overhead required by non-tail recursive functions could be
costly for large inputs. 

  example) Problem 1, Reverse a string recursively:

  /* From the API: String substring(int beginIndex, int endIndex)
   *      Returns a new string that is a substring of this string.
   *      The substring begins at the specified beginIndex and extends 
   *      to the character at index endIndex - 1.
   */

  public String reverseString(String word) {
     if(word == null || word.equals(""))
        return word;
     else
        return reverseString(word.substring(1, word.length())) + 
            word.substring(0,1);
  }

  example) Problem 2, Remove consecutive duplicates from a string recursively.
           For example, convert "aabccba" to "abcba":

  public String removeDuplicates(String word) {
     if(word == null || word.length() <= 1)
        return word;
     else if( word.charAt(0) == word.charAt(1) )
        return removeDuplicates(word.substring(1, word.length()));
     else
        return word.charAt(0) + 
            removeDuplicates(word.substring(1, word.length()));
   }


  example) Problem 3 (Compute n mod m without using %):
           Note: Divisor cannot be zero, otherwise in this code it would
                 be called recursively forever. Also,we may consider the case
                 that either val or divisor are negative. In this case, it is 
                 possible for this code to lead a stack overflow (i.e., the call
                 stack runs out of memory).

  public int modulus(int val, int divisor) {
     if(val < divisor)
        return val;
     else
        return modulus(val - divisor, divisor);
  }

  Suggested improvement:

  public int modulus(int val, int divisor) {
     if ( divisor==0 ) return 0;  // check for prevent from stack overflow.
                                  // It's better to raise an ArithmeticException 
                                  // in this case.
     boolean neg = val < 0;
     val = Math.abs(val);
     divisor = Math.abs(divisor);
 	
     if (val < divisor)
         return neg ? -val : val;
     else
 	return neg ? -modulus(val - divisor, divisor):
                    modulus(val - divisor, divisor);
  }

Is it possible to convert non-tail recursive functions into tail
recursive ones? The answer is usually yes. To illustrate the
process, we've redone Problem 1 using tail recursion and a helper
method. Below, reverseString is a 'hook,' which starts the actual
recursive calls with an initial value (sometimes the hook will pass
additional information):

  example) Poblem 4 -- redo Problem 1 with Tail Recursion:

  // Reverse a string (this is the hook):
  public String reverseString(String word) {
     return tailReverse(word, ""); // now call the recursion; the ""
                                   // helps to store the reversed letters
  }

  // Reverse letters in word, removing them from left to right one at
  // a time and adding from right to left in res:
  public String tailReverse(String word, String res) {
     if(word==null || word.equals("")) // null is no String; "" is empty String
        return res;
     else
        return tailReverse(word.substring(1, word.length()),
                   word.charAt(0) + res);
  }

  Suppose word is null, it is more reasonable to return null rather than an empty
  string. So the code above should change a little as follows:
 
  // Reverse a string (this is the hook):
  public String reverseString(String word) {
     if ( word == null ) return word;
     return tailReverse(word, ""); // now call the recursion; the ""
                                   // helps to store the reversed letters
  }

  // Reverse letters in word, removing them from left to right one at
  // a time and adding from right to left in res:
  public String tailReverse(String word, String res) {
     if( word.equals("") )         // null is no String; "" is empty String
         return res;
     else
         return tailReverse(word.substring(1, word.length()), 
                             word.charAt(0) + res);
  }

Some more examples:

  example) What is the result of mystery (2, 25)? mystery(3, 35)?
           Given positive integers a and b, describe what mystery(a, b) does.  
    
           mystery(2,25) = 50
           mystery(3,35) = 105
           mystery(a,b): multiplies a and b
  
  public int mystery(int a, int b)  {
        if (b == 0)         
            return 0;
        else if (b % 2 == 0) 
            return mystery(a + a, b / 2);
        else                 
            return mystery(a + a, b / 2) + a;
  }


  example) Find the gcd (greatest common divisor) of 2 numbers:

    public int gcd(int a, int b) {
        int remainder = a % b;

        if (remainder == 0)
            return b;
        else
            return gcd(b, remainder);
    }

  example) Write print out the binary representation of a given number:
           Note that the binary representation of 0 should be 0.

  public void convertBinary( int n ) {
     if( n<2 ) {
         System.out.println(n);
         return;
     }
     convertBinary(n/2);
     System.out.println(n % 2);
  }

  example) What is f(0)?
           f(0) = 997

    public static int f(int x) {
        if( x > 1000) 
            return x-4;
        else 
            return f(f(x+5));
    }

  example) Merge two strings that are ordered alphabetically. 
           The result should also be alphabetical.

  public String merge(String first, String second) {
     if(first ==null || first.equals(""))
          return second==null? first:second;
     else if (second == null || second.equals(""))
          return first;
     else if(first.charAt(0) < second.charAt(0))
          return first.charAt(0) + merge( first.substring(1, first.length()), second);
     else
          return second.charAt(0) + merge(first, second.substring(1, second.length()));
   }

  example) Given an array of characters and the length of the array, print out 
           all the permutations of the array. Hint: you might need a helper method.

  Our solution fixes the last element of the array instead of the first. You could 
  also fix the first letter.

  public void permute(char[] a, int length) {
     if (length == 1) {
        System.out.println(a);
        return;
     }
     for (int i = 0; i < length; i++) {
        swap(a, i, length-1);
        permute(a, length-1);
        swap(a, i, length-1);
    }
 }  
 
 public void swap(char[] a, int i, int j) {
    char c;
    c = a[i]; 
    a[i] = a[j]; 
    a[j] = c;
 }