Please create a dirctory named lab10 to put the files from this lab in!

Part 1: recurse a bit

  1. Compile and run the following program
    #include <cstdlib>
    #include <iostream>
    #include <string>
    using namespace std;
    
    
    double harm(int i, int N)
    {
      if (i > N) 
        return 0;
      return 1.0/i + harm(i+1,N);
    }
    
    int main()
    {
      int n;
      cin >> n;
      cout << "harm(" << n << ") = " << harm(1,n) << endl;
      return 0;
    }
    ... that computes the first n terms of the harmonic series, 1/1 + 1/2 + ... 1/n using a recursive function. Try it out on a few values, then try it on a big value. The program crashed, eh? Why? A running program has some fixed amount of space allocated to the stack of function calls. If you force a whole bunch of recursive calls like this, you exceed that space. That's called "blowing the stack". So we tend not to use recursion for things like this. But it's good practice for us!
  2. Now: keep an eye on the previous example, and provide a recursive (no loops allowed!) definition of the function printspaced in the program below that prints out its input array elements from index i to the end (the array has N elements total). Elements should be separated by spaces!
    #include <cstdlib>
    #include <iostream>
    #include <string>
    using namespace std;
    
    // prints the elements of array A (that has N elements) from index i to the end
    // should be space separated, and there should be a newline at the end.
    void printspaced(int* A, int i, int N);
    
    int main()
    {
      // Create a randomish array to use as input to printspaced
      srand(time(0));
      int N = 10 + rand() % 20, K = N / (2 + rand() % 5);
      int *A = new int[N];
      for(int i = 0; i < N; i++)
        A[i] = i % K;
    
      // Call printspaced (and cross fingers!)
      printspaced(A,0,N);
    
      return 0;
    }
    If you've done this right, printspaced should print out the array nicely, like this:
    ~/$ ./prog
    0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1     
    	  
  3. Going further (if you've finished Parts 2 and 3): make it print comma-separated!
  4. Going still further (if you've finished Parts 2 and 3): write a recursive (no loops allowed!) version of search (assume arrays of strings). I recommend starting with the following prototype:
    // In : array A of N elements, i such that 0<=i<=N, and search string x
    // Out: index k, i<= k < N, such that A[k] matches x, or N if no such k exists  
    int search(string* A, int i, int N, string x);

Part 2: sorting fish ... more cards? Really?

Check out this program, which is a start at implementing a game of Go Fish. Right now, the game simply deals out seven cards to two players, and prints out those players' hands. Modify the program so that the hands are printed out sorted by face value (smallest to largest) with ties broken by suit (clubs before diamonds before hearts before spades). So, for example, instead of seeing
~/$ ./prog
Player1:  Q♦  2♥  7♣  A♠  J♠  J♥  9♣
Player2:  2♣  8♥  2♠  8♣  Q♠  3♥  4♣
I should see
~/$ ./prog
Player1:  2♥  7♣  9♣  J♥  J♠  Q♦  A♠
Player2:  2♣  2♠  3♥  4♣  8♣  8♥  Q♠
BTW: These exact hands can be gauranteed by replacing srand(time(0)); with srand(100);. That might help with debugging!

Part 3: searching for fish ... yep, more cards!

Add on to your Part 2 solution so that the program alternately asks player1 and player2 to choose a face to ask for (2,3,...,10,J,Q,K,A are the possible responses), and responds with either "yes" or "go fish", depending. No matter which response, have the game simply deal the asking player another card, reprint (in sorted order of course), and continue. This should of course stop when the deck is empty.
~/$ ./prog
Player1:  3♦  4♠  5♥  6♥  J♣  J♠  A♠
Player2:  2♦  6♣  7♠  9♣  9♥  Q♣  A♦
Player1 choose card: Q
yes

Player1:  3♦  4♠  5♥  6♥ 10♥  J♣  J♠  A♠
Player2:  2♦  6♣  7♠  9♣  9♥  Q♣  A♦
Player2 choose card: Q
go fish

Player1:  3♦  4♠  5♥  6♥ 10♥  J♣  J♠  A♠
Player2:  2♣  2♦  6♣  7♠  9♣  9♥  Q♣  A♦
Player1 choose card:
To make your life a bit easier, and to allow you to concentrate on search, which is what this is really about, I'm gifting you the following function:
// In:  string s representing a face value or a full card (e.g. "10" or "J")
// Out: the facevalue (2-14) represented by the string 
int stringToFaceValue(string s);

int stringToFaceValue(string s)
{
  char c = s[0];
  int fv = c - '0';
  if (c == '1') fv = 10;
  if (c == 'J') fv = 11;
  if (c == 'Q') fv = 12;
  if (c == 'K') fv = 13;
  if (c == 'A') fv = 14;
  return fv;
}

Part 4: Going Further ... Go Fish

Now make a full Go Fish game. In the complete game you could have player2's cards not printed out, and have player2 just randomly choose a card from his desk to ask for.