Recursive Searching

Searching revisited

Linear searching of an array:

Iterative: start at one end, scanning the data for the value, and if found, stop and return the position.

Recursive: check first element for key, return position if found, otherwise search the remaining elements of the array

private int linearSearch( Object key, int pos){
   if(pos >= vec.length) {
      return -1;
   } else if (vec[pos].equals(key)) {
      return pos;
   } else {
      return linearSearch(key, pos+1);
   }
}

The invocation would be pos = myArray.linearSearch( value, 0); which introduces an additional parameter that is superfluous for the user.  So we define a public helper function:

public int linearSearch(Object key){
    return linearSearch(key, 0); //start at 0
}

Binary Search Revisited

Binary searching of an array:

Iterative: start at middle, if value found, stop and return the position, else determine whether to search top half or bottom half, tracking the boundaries of the search area

Recursive: if segment is empty, return -1; if middle of segment == key return position, otherwise search top half or bottom half

private int binarySearch(Object key, int lo, int hi){
   if(lo > hi) {
      return -1;
   } else {
      int mid = (lo+hi)/2;
      int comp = vec[mid].compareTo(key);
      if(comp == 0){
          return mid;
      } else if(comp < 0){
          return binarySearch(key, mid+1, hi);
      } else {
          return binarySearch(key, lo, mid-1);
   }
}

The invocation would be pos = myArray.binarySearch( value, 0, myArray.size()-1); which introduces an additional parameter that is superfluous for the user.  So define a helper function:

public int binarySearch(Object key){
    return binarySearch(key, 0, size-1);
}

Complexity Analysis on Recursion

The formal approach to determining the big-O complexity of an algorithm is to set up recurrence relations and solve them.

For the recursive linear search we have

T(n) = T(n-1) + 1
T(0) = 1

That is, the time for searching an array of size n is the time to search an array of size n-1 plus the cost of searching (checking or comparing) the first element which is constant. The cost for searching an empty array is constant as well.

Solving:
T(n-1) = T(n-2) + 1,
so T(n) = T(n-1)+1 = [T(n-2) + 1] + 1 = T(n-2) + 2,
and T(n-2) = T(n-3) +1
so T(n) = T(n-2) + 2 = [T(n-3) + 1]  +1 = T(n-3) + 3,

and in general T(n) = T(n-i) + i;
so finally T(n) = T(0) + n = 1 + n = O(n)

 

 

Recursive Binary Search Analysis

For the recursive binary search we have

T(n) = 1 + T(n/2)
T(1) = 1

"The time to search n elements is a constant computation plus the time it takes to search n/2 elements."

Solving (rather intuitively) and assuming n is an even power of two (if not, we add dummy elements to the array to make it a size that is the next even power of two)

T(n/2) = 1  + T(n/4),
and T(n/4) = 1 + T(n/8), etc.

So T(n) = 1 + T(n/2) = 1 + 1 + T(n/4) = 1 + 1 + 1 + T(n/8)
and the pattern is T(n) = k + T(n/2^k)
now when k = log n, then n/(2^{log n})=n/n = 1,
so T(n) = log n + 1 = O(log n)

Recursive Complexity Patterns

When you have simple recurrence relations of the form

• T(n) = T(n-1) + f(n), then you have complexity of O(n*f(n))
• T(n) = T(n/k) + f(n), then you have complexity of O(log_k n * f(n))

Recursive factorial computation is of what complexity?

Consider the Fibonacci sequence recursive calculation:

F(1) = 1
F(2) = 1
F(n) = F(n-1)+F(n-2)

Its recurrence relation time is

T(1) = 1
T(2) = 1
T(n) = T(n-1) + T(n-2) + 1

Solving is a little beyond this course, but T(n) = O(2ⁿ) or "exponential"