Iteration vs. recursion¶

Iterative problems can be switched to recursion and the other way around. Both approaches can be used to either decrease- or divide-and-conquer.

Consider for example, the Search and BinarySearch algorithms below.

Search

1
2
3
4
5
6
7

  Search(Int a, Array N):
   FOR elem IN N:
     IF elem == a:
       return true
     END IF
   END LOOP
   return false

Binary search

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

  BinarySearch(A, left, right, value)
   (A in ascending order)
   if left = right then
     if A[left] = value then
         return true
     else
         return false
   else
     middle := ⌊(left+right)/2⌋
     if value ≤ A[middle] then
         return BinarySearch(A, left, middle, value)
     else
         return BinarySearch(A, middle+1, right, value)

The first one uses iteration, the second one, recursion. Another difference between the two algorithms is the efficiency: logarithmic BinarySearch is asymptotically more efficient than linear Search. On the other hand, Search does not set any prerequisites for the order the items are in prior to the search. BinarySearch uses divide-and-conquer principle, whose benefits become the clearer the more data one has to scan through.

searchSmallestMissingIteration()¶

Implement the algorithm searchSmallestMissingIteration() in the file wk02_decrease_or_divide/missing/missing.cc.

int searchSmallestMissingIteration(int* arr, int size) {
  // returns the first missing number, or NO_VALUE_MISSING if not found
  return NO_VALUE_MISSING;
}

The parameter arr is the array to be checked, and size is the array size.

Write your solution for searchSmallestMissingIteration() in C++ using decrease-and-conquer principles.

searchSmallestMissing()¶

Implement the algorithm searchSmallestMissing() in the file wk02_decrease_or_divide/missing/missing2.cc.

int searchSmallestMissing(int* A, int left, int right) {
  // returns the first missing number, or NO_VALUE_MISSING if not found
  return NO_VALUE_MISSING;
}

The parameters:

• A is the array to be checked
• left the leftmost index of an array, initially 0
• right the rightmost index of an array, initially size-1 when size is the array size.

Write your solution for searchSmallestMissing() in C++ using divide-and-conquer principles.

Quicksort¶

Mergesort¶