Recursive Algorithms

Recursion is a powerful problem solving tool. In this lesson we consider few well-known recursive algorithms. We present them first, since it is easy to understand why they are recursive. Recursive definitions are in fact mathematical definitions that can be directly translated into code and also prove the correctness. Let us start with Binary Search Algorithm.

Binary Search Algorithm

Looking up a word in the telephone directory? Here is the perfect algorithm. Find the middle of the directory. If the word you are searching is alphabetically higher than the middle word, then focus only on the right half of the book, else focus on the left half of the book. Who knows, you may be lucky and find the word in the middle. If you don’t find the word, then focus on half the directory and continue the same process. The key here is that every search effort reduces the search area by a half. So if we are dealing with a data set of size 10²⁰ (that is about a million records), the word can be found or we can determine that the word is not in the directory in no more than 20 comparisons. Only assumption you are making here is that directory is a sorted list. Here is an algorithm for searching a dictionary (or directory)

Algorithm:

 
Search(dictionary)
{
   if (Dictionary has only 1 page)
      Sequentially search page for word
   else
   {
      Open the dictionary to the middle page
      Determine which half of the dictionary the word is in
      if (The word is in the first half)
         Search(first half of dictionary)   // ignore second half
      else
         Search(second half of dictionary   // ignore first half
   }
}

Note that the problem presents all characteristics of a recursive algorithm. It does have a terminal case to end recursion and it does express the solution to larger problem using solution to one or smaller sub problems. One of the important assumptions we made about the binary search here is that list is sorted. Binary search cannot be performed if the list is not sorted. Binary search is recursive (it can be implemented iteratively as well) and its complexity is O(log n) compared to the complexity of linear search that is of O(n).

Factorial

Factorial is an important mathematical function. A recursive definition of factorial is as follows.

The above definition can be directly translated into code as follows. Note that we have a base case as well as a recursive case.

 
main()
{
 int i = 3;                 // 1
 cout << f(i) << endl;      // 2
}
int f(int a1)
{
   if (a1 <= 1)               // 3
      return 1;               // 4
   else                       // 5
      return a1 * f(a1 - 1);  // 6
}

Non-recursive version:

int fact(int n)
{
   int i;
   int prod = 1;
   for (i = 1; i <= n; i++)
 prod *= i;
   return prod;
}

The Fibonacci Sequence

Fibonacci Definition:

Consider:

int fib(int val)
{
   if (val <= 2)
      return 1;
   else
      return fib(val - 1) + fib(val - 2);
}

Call graph for fib(6):

Non-recursive version:

int fib(int val)
{
 int current = 1;
 int old = 1;
 int older = 1;
 val -=2;
   while (val > 0)
   {
      current = old + older;
      older = old;
      old = current;
      --val;
   }
   return current;
}

Greatest Common Divisor

Definition:

int gcd(int a, int b)
{
 int remainder = a % b;
   if (remaider == 0)
      return b;
   else
      return gcd(b, remainder);
}