Notes App. C:
Addendum to Essentials of Data Structures, Appendix C

Math 61 -- D. C. Smolarski, S.J.
Santa Clara University, Department of Mathematics and Computer Science

Contents

• Recursive Binary Search (C-2)
• A Naturally Recursive Problem: Fibonacci Numbers (C-3)
• Towers of Hanoi (C-6)
• Evaluating Recursive Functions, Stacks (C-7, C-8)

Recursive Binary Search

See Ford & Topp, pg 498, for a discussion of the following code.

        // recursive version of the binary search to locate
	// a key in ordered array A
	template <class T>
	int BinSearch(T A[], int low, int high, T key)
	{
	   int mid;
	   T midvalue;

	   // stopping condition : key not found
	   if (low > high)
	      return (-1);

	   // compare against list midpoint and subdive
	   // if a match does not occur.  apply binary
	   // search to the appropriate sublist
	   else
	   {
	      mid = (low + high)/2;
	      midvalue = A[mid];
	      // stopping conditioin : key found
	      if (key == midvalue)
	         return mid;  // key found at index mid

	      // look left if key < midvalue; otherwise, look right
	      else if (key < midvalue)
	         // recursive step
		 return BinSearch(A,low,mid-1,key);
	      else
	         // recurseive step
		 return BinSearch(A,mid+1,high,key);
           }
	}

A Naturally Recursive Problem: Fibonacci Numbers

The C++ recursive code can be found in Notes N19 for Math 10 (this link).

The same program in Fortran-90 can be found in the Math 60 Notes: Chapter 10 B (this link).

Towers of Hanoi

The Ford & Topp text has a version of the code on page 513 ff which uses a specially-defined class called "strclass" (cf. page 338). The following is an alternative version which matches the code in App. C more closely (the code may be accessed at this link for running):

    #include <iostream.h>

    void hanoi(int n, char frompeg, char topeg, char auxpeg)
    {
      if (n == 1) 
         cout << "move disk 1 from peg " << frompeg 
	      << " to peg "<< topeg <<endl;
      else {
         hanoi(n-1, frompeg, auxpeg, topeg);
         cout << "move disk " << n << " from peg " << frompeg 
              << " to peg " << topeg << endl;
         hanoi(n-1, auxpeg, topeg, frompeg);
         }
    }  /* end towers */

    int main()
    {   int n;
        n = 5;
        hanoi(n, 'a', 'c', 'b');
    } 

The same program in Fortran-90 can be found in Notes: Fortran-90 and Recursion (this link).

Evaluating Recursive Functions, Stacks

Equivalent code in C++ for Example 2 (pg 175 and explained in section C-8) can be found in Math 10, Notes N19 (via this link). In Essentials the routine is called "Mystery," whereas in Notes N19, it is called "StackTheCharacter."

This page is maintained by Dennis C. Smolarski, S.J.
© Copyright 1998, 1999 Dennis C. Smolarski, SJ, All rights reserved.
Last changed: 27 March 1999.