// fib.cpp

#include <iostream>
#include <vector>
using namespace std;

//  ASSUME: n is non-negative
//
//           -
//          /  0                 if n == 0
//         /
// f(n) = <    1                 if n == 1
//         \
//          \  f(n-1) + f(n-2)   if n > 1
//           -
//
// Write a recursive function and call it from
//   main() with various values of n
int f( int n )
{
  if ( n <= 1 ) {
    return n;
  } else {
    return f( n - 1 ) + f( n - 2 );
  }
}

// Recursive function to generate a vector of
//   the fibonacci sequence up to n
//
// THIS DOES NOT WORK!  ANALYZE AND SEE WHY.
//
int f_vector( vector<int>& v, int n )
{
  int result;
  if ( n <= 1 ) {
    result = n;
  } else {
    result = f_vector( v, n - 1 ) + f_vector( v, n - 2 );
  }
  v.push_back( result );
  return result;
}

// Boolean Search
//
// Here is the recursive helper function.  If x is in the vector, then
// it must be located within the subscript range low to high. Therefore,
// when low and high are equal, their common value is the only possible
// place for x.  Otherwise, the middle value is checked, and the search
// continues recursively in either the lower or upper half of the given
// vector.
//
bool
binsearch( const vector<int> &v, int low, int high, int x )
{
  if ( high == low ) {
    return x == v[low];   // did we find x?
  }

  int midpoint = ( low + high ) / 2;

  // recursively call binsearch() with half the given vector
  if ( x <= v[midpoint] ) {
    return binsearch( v, low, midpoint, x );
  } else {
    return binsearch( v, midpoint + 1, high, x );
  }
}

// Boolean Search
//
// The driver function establishes the search range for the value of x
// based on the minimum and maximum subscripts in the vector.
//
         // const here means that function will NOT change
bool    //  the vector back in main().
binsearch( const vector<int> &v, int x )
{
  return binsearch( v, 0, v.size() - 1, x );
}


int main()
{
  int n;
  cout << "Enter non-negative integer: ";
  cin >> n;

  int r = f( n );
  cout << "f( " << n << " ) is " << r << endl;

  // Use recursive function f_vector()
//  vector<int> fib;
//  f_vector( fib, n );

  // Create vector of fibonacci sequence:
  vector<int> fib;
  for ( int i = 0 ; i <= n ; i++ ) {
    fib.push_back( f( i ) );
  }

  // Display vector:
  for ( int i = 0 ; i < fib.size() ; i++ ) {
    cout << fib[i] << ' ';
  }
  cout << endl;

  int x;
  cout << "Search this vector for: ";
  cin >> x;
  cout << "Found? " << binsearch( fib, x ) << endl;

  return 0;
}