David E. Goldschmidt, Ph.D.

Example 11: Sorting Vectors of Strings

// alpha.cpp  <== click here for file

// Example names.txt file serves as input.

#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// use this later....
bool sort_reverse( string const &left, string const &right );

int main( int argc, char* argv[] )
{
  if ( argc != 3 )
  {
    cerr << "USAGE: " << argv[0] << " <names-in> <names-out>\n";
    return 1;
  }

  // open a file for reading
  ifstream names_in( argv[1] );
  if ( !names_in )
  {
    cerr << "ERROR: cannot open file " << argv[1] << '\n';
    return 1;
  }

  // open file for writing
  ofstream names_out( argv[2] );
  if ( !names_out )
  {
    cerr << "ERROR: cannot open file " << argv[2] << '\n';
    return 1;
  }

  vector<string> names;
  string one_name;

  // read from the file
  while ( names_in >> one_name )
  {
    names.push_back( one_name );
  }

  sort( names.begin(), names.end() );

  // sort in reverse order using the sort_reverse() function
//  sort( names.begin(), names.end(), sort_reverse );


  // echo back the sorted list
  for ( int i = 0 ; i < names.size() ; i++ )
  {
    names_out << names[i] << '\n';
  }

  return 0;
}

bool
sort_reverse( string const &left, string const &right )
{
  return right < left;

//  return empl_left.id < empl_right.id;
//  return empl_left.lname < empl_right.lname;
}

Different Ways to Sort:

• By default, sort() will sort strings alphabetically.
• Using a function (sort_reverse() in the above example), we can define how the sort() algorithm sorts. In particular, the sort_reverse() function defines how to compare two elements, left and right.

Example 12: Recursion

// factorial.cpp  >== click here for file

#include <iostream>
using namespace std;

int factorial( int n );
int factorial_recursive( int n );

int main()
{
  int x;
  cout << "Enter an integer: ";
  cin >> x;
//  cout << x << "! is " << factorial( x ) << endl;
  cout << x << "! is " << factorial_recursive( x ) << endl;
  return 0;
}

int factorial_recursive( int n )
{
  if ( n == 0 ) {
    return 1;
  } else { // n > 0
    return n * factorial_recursive( n - 1 );
// e.g. if n is 6:
//        return 6 * 5 * 4 * 3 * 2 * 1 * 1
  }
}

int factorial( int n )     // THIS ONE IS FASTER (most likely)
{
  int result = 1;
  for ( int i = n ; i > 1 ; i-- )
  {
    result = result * i;
  }
  return result;
}

Recursion:

• The factorial is defined for non-negative integers as follows:

            -
           /
          |   1                if n == 0
  n!  =  <
          |   n * (n - 1)!     if n > 0
           \
            -

• Similarly, computing integer powers is defined as follows:

            -
           /
   p      |   1                if p == 0
  n   =  <         p-1
          |   n * n            if p > 0
           \
            -

• These are both examples of recursive definitions.
• C++, like other modern programming languages, allows functions to call themselves. This is called recursion and gives a direct method of implementing recursive functions.

Calling a Function:

• When a program makes a function call, the program creates an activation record to keep track of:
  1. Each newly called function's own completely separate instances of parameters and local variables.
  2. The location in the calling function code to return to when the newly called function is complete.
  3. Which activation record to return to when the function is done.
• Calling a recursive function is no different. Each function call has its own separate memory space with its own separate instances of parameters and local variables.
• For example, if we call a fact() function with 4 as the input parameter, we ultimately get 24 as the correct result, as illustrated in the following diagram. In the diagram, each box is an activation record, the solid lines indicating function calls, the dashed lines indicating the returns.
• In general, all of the recursive calls stack up, then unravel, producing one final result (and maybe some additional side effects, if desired).

Rules for Writing Recursive Functions:

• Rules for writing recursive functions:
  1. Handle the base case first. This is your stopping point (e.g. when n == 0 or when size == 1).
  2. Break the problem down into smaller and smaller pieces.
  3. Make sure each recursive call progresses toward the base case.
  4. Identify what needs to be done before calling the recursive function. And is a helper function needed?
  5. Determine what needs to be done after the series of recursive function calls are made.

Iteration vs. Recursion:

• All of the above functions could have also been written using a for loop or a while loop (i.e. iteratively).
• Iterative functions are generally faster than their corresponding recursive functions.
• Compiler optimizations sometimes (but not always!) can take care of this by automatically interpreting and eliminating the recursion.
• Sometimes writing recursive functions is more natural than writing iterative functions.