title: Ordered Binary Search w/ Assembly | Recursive vs. Iterative vs. Library
body: <p>Which is better?</p>
  
  <p>According to Savitch, each recurse is saved on the stack in the form of an activation frame.  This has overhead.  However it takes a few less lines of code to write a recursive version.  For an interview which one is better to turn in.  The code for both is below.</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  using namespace std;
  const int SIZE = 10;
  int array[ SIZE ] = { 0,1,2,3,4,5,6,7,8,9 };
  int answer = NULL;
  
  void binary_search_recursive( int array[], int start, int end, int value, int&amp; answer )
  {
      int mid = (start + end ) / 2;
  
      if ( array[ mid ] == value )
      {
          answer = mid;
      }
      else if ( array[ mid ] &lt; value )
      {
          binary_search_recursive( array, mid + 1, end, value, answer );
      }
      else
      {
          binary_search_recursive( array, start, mid - 1, value, answer );
      }
  }
  
  void binary_search_iterative( int array[], int start, int end, int value, int&amp; answer )
  {
      int mid = ( (start + end ) / 2 );
  
      while( array[ mid ] != value  )
      {
          if ( array[ mid ] &lt; value )
          {
              start = mid; 
              mid = ( ( ( mid + 1 ) + end ) / 2 );
          }
          else
          {
              end = mid;
              mid = ( ( start + ( mid - 1 ) ) / 2 );
          } 
      }
      answer = mid;
  }
  
  int main()
  {
      binary_search_iterative( array, 0, SIZE - 1, 4, answer);
      cout &lt;&lt; answer;
      return 0;
  }
  </code></pre>