Review: functions

When a function A calls another function B

Execution is suspended in function A.

The instructions in function B are executed.

Control returns to function A and execution resumes after the function call.

  void foo(void)
  {

    cout << "In foo(), before bar()" << endl;

    bar();

    cout << "In foo(), after bar()" << endl;
  
  }

  void bar(void)
  {
    cout << "In bar()" << endl;
  }

    In foo, before bar()
    In bar()
    In foo, after bar()

Review: objects

Remember that an object must be declared before it can be used.

There are three ways that an object can be declared for use in a function

It can be declared globally.

It can be passed as a parameter to the function.

It can be declared in the function.

Objects declared in a function only exist in that function.

They are created at the time that the function is called.

They are destroyed when the function has finished executing.

They are different objects each time that the function is called.

They cannot be accessed by other functions, unless they are passed as parameters to that function.

When an object is declared

Some piece of memory is reserved for it

The identifier we specify the variable is essentially a name for that memory.

Picture

The stack

The stack pointer

When a function is called - space is allocated, constructors are called

When the function exits - space is deallocated, destructors are called

  void foo(void)
  {
     int a;
     int b;

     a = 5;
     b = 7;

     bar(20);

     baz(37, 49);
  }

  void bar(int a)
  {
    int b;

    b = a;
  }

  void baz(int a, int b)
  {
    int c;
    int d;

    c = a + b;
    d = a - b;
  }

Recursion

Recursion is what we call it when a function calls itself

When a function calls itself

It is exactly the same as if it called a different function, except

The other function being called is the same as the one doing the calling, but

The objects being referenced are different

Why? Because of the stack implementation of function calls

So, what's the big deal with recursion?

It's a fairly simple idea

It is extremely powerful

It greatly simplifies some programming problems.

The basic idea is that you

Specify the anchor, or trivial case that explicitly defines the function for some trivial value.

Specify the inductive or non-trivial case, that defines the function in terms of the parameters and the value of other simpler calls to the function.

Example: Computing factorials

Remember that the factorial of n, written n! is the product n * n-1 * ... * 2 * 1

The iterative version:

  int factorial(int n)
  {
    int i; 
    int fact = 1;

    for(i = 1; i <= n; i++)
      fact = fact*i;

    return(fact);
  }

  int factorial(unsigned int n) 
  {
    int fact;

    if(n == 0)    // the anchor case
      fact = 1;
    else          // the inductive case
      fact = n * factorial(n-1);

    return(fact);
  }

It's also clear that the second version is much easier to understand and more closely matches the mathematical definition of factorial.

What happens without the anchor case?

What happens with the stack if we execute factorial(3)? (Picture)

Example: computing exponentials

  int power(unsigned int n, int pow)
  {
    if(pow == 0)    // anchor case
      return(1);
    else            // inductive case
      return(n * power(n, pow-1));
  }

Example: printout out a binary number without leading zeroes

  void print_binary(unsigned int n) 
  {
    int binary_digit;

    if(n > 0) {
      binary_digit = n & 1;

      print_binary(n >> 1);

      cout << binary_digit;
    }

    return();
  }

Fibonacci numbers revisited

Remember from quiz 2 that Fibonacci numbers are a sequence of numbers defined as follows: the first and second Fibonacci numbers are 1. Every other Fibonacci number is defined to be the sum of the previous two Fibonacci numbers. So, the sequence begins 1, 1, 2, 3, 5, 8, 13, 21, ...

Iterative solution:

int fibonacci(unsigned int n) 
{  
  int fib;
  int last;
  int temp;

  switch(n) {
    case 0:
      fib = 0;
      break;

    case 1:
      fib = 1;
      break;
 
    case 2: 
      fib = 1;
      break;

    default:
      // initialize fib
      fib = 1;
      last = 1;

      for(i = 2; i < n; i++) {
        temp = fib;
        fib += last;
        last = temp;
      }
      break;
  }

  return(fib);
}

int fibonacci(unsigned int n)
{
  switch(n) {
    case 0: 
      return(0);
      break;

    case 1:
      return(1);
      break;

    case 2: 
      return(1);
      break;

    default:
      return( fibonacci(n-1) + fibonacci(n-2) );
      break;
  }
}

Binary Search

If we know that the list is in sorted order, then we can do binary search, which has better average and worst case behaviour than linear search.

In binary search, we:

Look at the middle element of the list.

If it is the value we are looking for, we are done.

If the value we are looking for is smaller than the middle element, then we continue with the bottom half of the list.

If the value we are looking for is larger than the middle element, then we continue with the top half of the list.

  int binary_search(int list[], int start, int end, int m)
  {
      int i;
      int N = end - start;
      int midval;

      // anchor case

      if(N == 0) {
        if(list[start + N] == m)
          return(start + N);
        else
          return(-1);
      }
     

      // inductive cases

      midval = list[start + N/2];

      if( midval == m )

          return( start + N/2 );

      else if( midval > m)

          return( binary_search(list, start, start + N/2 - 1, m) );

      else

          return( binary_search(list, start + N/2 + 1, end, m) ); 
  }

Quicksort

Quicksort is an extremely efficient sorting method that is a natural for implementation using recursion

In quicksort, we

Select a pivot value

Arrange the list such that

Everything to the left of the pivot has a smaller value

Everything to the right of the pivot has a larger value

Repeat the algorithm on the left and right sublists

  void quicksort(int list[], int start, int end)
  {
    int mid;

    if(start != end) {

      mid = split(list, start, end);

      quicksort(list, start, mid-1);

      quicksort(list, mid+1, end);

    }
  }


  int split(int list[], int start, int end)
  {
    int left = start;
    int right = end;
    int pivot = list[start];
    int temp;

    while(left < right) {

      // scan to the right looking for a value smaller than the pivot
      while(list[right] > pivot)
        right--;

      // scan to the left, looking for a value larger than the pivot
      while( (left < right) && (list[left] <= pivot) )
        left++;

      if(left < right) {
        // swap list[left] and list[right]
        temp = list[left];
        list[left] = list[right];
        list[right] = temp;
      }
    }      

    list[start] = list[right];
    list[right] = pivot;

    return(right);

  }