CS 3343/3341
  Introduction to Algorithms  
Spring 2012
Elementary
  Recursion Examples  

Note: This page shows elementary examples. Much more complex algorithms often involve recursion in a significant way. Examples you should already have seen include binary tree traversals and sorting algorithms such as quicksort. Other examples include especially those from programming languages and compilers.

Number Base Conversion: If you don't look at all of these examples, you should definitely work through this one as the most elementary and accessible.

Binary Search: This is another extended example that you should definitely look at. It presents several more-comlex issues than the previous example.
Factorial: The factorial of an integer n, denoted by n!, can be defined by the equation:

We can use this definition to write a function in either C or Java:

int fact(int n) {
   int res = 1;
   for (int i = n; i >= 1; i--)
      res *= i;
   return res;
}

The above definition isn't satisfactory from a logical point of view. It seems to say that 2! = 2∙1∙0∙...∙3∙2∙1, where we need to fill in something for the three dots. Of course we know what the notation means, but a better and more logical definition is a recursive one:

This uses factorial to define factorial, but it uses a smaller instance. We can pattern a function in either C or Java after this definition:

int fact(int n) {
   if (n == 1) return 1;
   return n * fact(n-1);
}

Fibonacci numbers:
Recursive Reversal of a String. Here is another illustration of recursion in action.

// ReverseString: test a recursive method to reverse a String
//   Uses the String method substring.
//    s.substring(i) goes from index i to the end.
//    s.substring(i, j) goes from index i up to but not including index j

public class ReverseTest {

   // recursive string reversal
   public static String reverse(String s) {
      if (s.length() == 1) return s;
      char ch = s.charAt(0);
      String res = reverse(s.substring(1)) + ch;
      return res;
   }

   // recursive: get rid of unnecessary local variables
   public static String reverse2(String s) {
      if (s.length() == 1) return s;
      return reverse(s.substring(1)) + s.charAt(0);
   }

   // recursive: work from the other end
   public static String reverse3(String s) {
      if (s.length() == 1) return s;
      return s.charAt(s.length() - 1) +
         reverse(s.substring(0, s.length() - 1));
   }

   // NON-RECURSIVE: just concatenate chars in opposite order
   public static String reverse4(String s) {
      String res = "";
      for (int i = 0; i < s.length(); i++)
         res = s.charAt(i) + res;
      return res;
   } 

   public static void main(String[] args) {
      String str = "The quick brown fox jumps over the lazy dog.";
      System.out.println(str);
      System.out.println(reverse (str));
      System.out.println(reverse2(str));
      System.out.println(reverse3(str));
      System.out.println(reverse4(str));
   }
}

Here is the output:

The quick brown fox jumps over the lazy dog.
.god yzal eht revo spmuj xof nworb kciuq ehT
.god yzal eht revo spmuj xof nworb kciuq ehT
.god yzal eht revo spmuj xof nworb kciuq ehT
.god yzal eht revo spmuj xof nworb kciuq ehT

Revision date: 2011-11-27. (Please use ISO 8601, the International Standard Date and Time Notation.)