Iteration vs. recursion¶

Iterative problems can be switch 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.

Function searchSmallestMissingIteration()/searchSmallestMissing()

Let us consider similar problem, where an algorithm searches smallest missing value, and takes an array of unique integer numbers in ascending order as a parameter.

For example, with the input of [0, 1, 2, 3, 4, 5, 12, 23], searchSmallestMissing() function returns 6. If no value is missing, then function must return NO_VALUE_MISSING.

Can you figure out two solutions?

• One that uses iteration
• Another that uses recursion

Quicksort¶

Mergesort¶