Introduction to Computer Science:
Assignment 22a:  For Loops and i++
Assignment 22b:  Recursion Fundamentals
 Sewickley Academy, 2000-2001

See Course Home Page.
 
Date Assigned: Sat Nov-18
Date Due: Tue Nov-21

Assignment 22a:  For Loops and i++

1.  Discussion of For Loops

Thus far, we always construct loops using while statements.  The classic loop is to iterate over all the elements in a vector, which is done as follows:

int i, len;
len = v.length();
i = 0;
while (i < len)
{
    doSomethingToTheVectorAtIndexI(v,i);
    i = i + 1;
}
It turns out that this is so common a pattern that there is a special statement, for, to make this more concise.  A for loop is expressed as follows:
for (<initialization>; <test>; <increment>)
{
    <body>;
}
This is identical to the following while loop:
<initialization>;
while (<test>)
{
    <body>;
    <increment>;
}
If these are identical, then why bother with a for statement, since it is definitely true that anything you can do with a for statement can also be done with a while statement.  The answer is twofold:  (1) because sometimes it is more convenient and concise to use a for statement; and (2) because it is part of the language, and it is used by programmers everywhere, so, realistically, you pretty much have to understand how it works.

Let's return to the classic while loop:

int i, len;
len = v.length();
i = 0;
while (i < len)
{
    doSomethingToTheVectorAtIndexI(v,i);
    i = i + 1;
}
Using the pattern we just learned, this is how the same loop is constructed as a for loop.  Note that the equivalent expressions in each loop are highlighted in the same color.
int i, len;
len = v.length();
for (i=0; i<len; i = i + 1)
{
    doSomethingToTheVectorAtIndexI(v,i);
}
Study these two code fragments carefully to understand precisely how they are semantically identical.

2.  Discussion of i++

Here we learn another new construct:  i++.  For our purposes now, this is equivalent to i = i + 1.  That's it.  So the preceding for loop may be rewritten as:

int i, len;
len = v.length();
for (i=0; i<len; i++)
{
    doSomethingToTheVectorAtIndexI(v,i);
}
This is how you will generally see the "classic loop" written by professional developers, and how you are expected to write this loop henceforth.

So, if i++ is equivalent to i = i + 1, then why would we bother to learn the new construct?  As with the for loop versus a while loop, the i++ construct is a bit more concise and is also used by programmers everywhere.  That is reason enough.

There is a third reason, however:  it turns out that i++ is not exactly equivalent to i = i + 1.  However, that discussion is outside the scope of this course (at least at this time), as we presently will not use i++ in a way that i = i + 1 would not work as well.

Two final notes:  first, there is a similar construct, ++i, which is not exactly equivalent to i++, but for our purposes at this time can be considered equivalent.  However, while you will surely see this construct used frequently in code written by others, for code which you write you are advised to use i++ for now.

Second, there is another construct, i--, which is analogous to i++ by which decrements rather than increments.  So, i-- is roughly equivalent to i = i - 1.  And there is also --i, but you are to use i-- for now.

3.  Convert the while loops to equivalent for loops in the code below, and convert the i = i + 1 statements to i++ statements (note that this applies to any variable, not just i), and the i = i - 1 statements to i-- statements.

Note: You must convert the loops exactly according to the pattern given above.  You may not restructure the loop in any way except to convert from a while loop to a for loop.  Specifically, if the loop counts downwards rather than upwards, it must still do so following your conversion.

Hint:  As needed in the main() loop, to convert a loop of the form while (true) into a for statement, you may wish to use a null statement.  This is just a semicolon.  It means:  do nothing.  It is useful when the syntax requires that you provide a statement, such as an initialization in a for loop, but you have nothing useful to put there.  Then, just use a null statement.

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include "apvector.h"

typedef apvector<int> intVector;
typedef intVector& intVectorByReference;

const int MAX_ELEMENTS_PER_LINE = 18;
const int BIG_NUM = 99;

void printVector(intVectorByReference v)
{
 int i,len;
 len = v.length();
 i = 0;
 while (i < len)
 {
  // output a comma before every element
  // except the first one
  if (i > 0)
   cout << ", ";

  // output a newline after every
  // MAX_ELEMENTS_PER_LINE elements
  if ((i > 0) && (i % MAX_ELEMENTS_PER_LINE == 0))
   cout << endl;

  // finally, output this element
  cout << v[i];

  // and increment the index
  i = i + 1;
 }
 // print terminating newline
 cout << endl;
}

void selectionSort(intVectorByReference v)
{
 int cursor,i,len,smallestIndex,temp;
 len = v.length();
 cursor = 0;
 while (cursor < len-1)
 {
  // 1.  Find smallest element to right of cursor
  smallestIndex = cursor;
  i = cursor+1;
  while (i < len)
  {
   if (v[i] < v[smallestIndex])
   {
    smallestIndex = i;
   }
   i = i + 1;
  }

  // 2. Swap smallest element with v[cursor]
  temp = v[cursor];
  v[cursor] = v[smallestIndex];
  v[smallestIndex] = temp;

  // 3.  Increment cursor to continue
  cursor = cursor + 1;
 }
}

void loadVectorWithRandomElements(intVectorByReference v)
{
 // Be careful here -- note that we are
 // not counting from 0 to (len-1), but we
 // are counting *down* from (len-1) to 0...

 int i, random;
 i = v.length() - 1;
 while (i >= 0)
 {
  // find a random number in [0,RAND_MAX)
  random = rand();
  while (random == RAND_MAX)
  {
   random = rand();
  }
  // convert this to range [0,BIG_NUM]
  v[i] = int((double(random)/RAND_MAX) * (BIG_NUM+1));
  i = i - 1;
 }
}

void main()
{
 intVector v;
 int len;
 while (true)
 {
  cout << "Enter the length of the vector (<0 to exit): ";
  cin >> len;

  if (len < 0)
   return;

  v.resize(len);

  loadVectorWithRandomElements(v);
  printVector(v);

  selectionSort(v);
  printVector(v);
 }
}

Assignment 22b:  Recursion Fundamentals

4.  Discussion of Recursion

As we covered in class, a function is called recursive if it calls itself.  For example, consider the following non-recursive function which takes two numbers, x and y, and computes the power function xy:

int power(int x, int y)
{
 int result, counter;
 result = 1;
 for (counter=0; counter<y; counter++)
 {
  result = result * x;
 }
 return result;
}
This function works by counting from 0 to (y-1), and on each iteration multiplying the result by x.  Thus, in the end, this function multiplies x together y times, hence computing xy.  Because this function iterates through iterations, it is called (imagine!) iterative.  Thus, for loops and while loops are iterative constructs.

We can defined the power function another way, however, based upon itself.  We can say that power(x,y) is simply x times power(x,y-1).  Consider:  35 is really just 3 * 34, right?  More generally, 3y = 3 * 3y-1.  Of course, this works not just for 3, but for any number x, so we get:  xy = x * xy-1.

So far, so good.  Now we know that power(x,y) computes xy, so we can restate the conclusion from the preceding paragraph as follows: power(x,y) = x * power(x,y-1).  This is a recursive definition of the power() function.  It is recursive because we have defined the function in terms of itelf!

Now, how would we write such a function in C++?  Easy:

int power(int x, int y)
{
    int result;
    result = x * power(x,y-1);
    return result;
}
Study this function to understand how it computes the power recursively.  Unfortunately, it doesn't work.  It almost works, but consider the following trace when we call power(2,3) to compute 23:
power(2,3) is called
it wants to set result to 2 * power(2,2), thus...
    power(2,2) is called
    it wants to set result to 2 * power(2,1), thus..
        power(2,1) is called
        it wants to set result to 2 * power(2,0), thus....
            power(2,0) is called
            it wants to set result to 2 * power(2,-1), thus....
                power(2,-1) is called
                it wants to set result to 2 * power(2,-2), thus...
                    power(2,-2) is called
                    yikes, this could go on for a while!!!
This is called infinite recursion.  This program will run until it gets a stack overflow and crashes.  Eeek.  What went wrong?  If you look at the trace above, you will see a point where we did something silly.  What is power(2,0)?  That is, what is 20?  It is 1, of course.  Rather than recursively call power(2,-1) at that point, we should just return 1.  This is known as our base case.  It is what stops recursion from going on forever.  All recursive functions must test for their base case first.

Let's do that here.  We modify power() to first test if the exponent (y) is less than or equal to 0, and we return 1 as our result in that case.

int power(int x, int y)
{
    int result;
    if (y <= 0)
    {
        // This is our base case.
        // We may not recurse here.
        result = 1;
    }
    else
    {
        // Here is the recursive case.
        result = x * power(x,y-1);
    }
    return result;
}
This fixes the problem.  To see why, consider the following trace again for 23:
power(2,3) is called
it wants to set result to 2 * power(2,2), thus...
    power(2,2) is called
    it wants to set result to 2 * power(2,1), thus..
        power(2,1) is called
        it wants to set result to 2 * power(2,0), thus....
            power(2,0) is called
           this is the base case, and it returns 1
        Thus, power(2,1) return 2*1 = 2
    Thus, power(2,2) returns 2*2 = 4
Thus, power(2,3) returns 2*4 = 8.
Notice that our base case tests if (y <= 0) rather than simply if (y == 0).  This is convenient in case the user enters a negative exponent.  Our code is not built to properly compute negative exponents (extra credit if you fix that problem in your recursive function), such as 3-5, but by catching it in the base case, we at least do not enter an infinite recursion in that case (we just return 1 as the erroneous result).

Here, then, is a simple program which uses the recursive power() function we just defined:

#include <stdio.h>
#include <iostream.h>

int power(int x, int y)
{
    int result;
    if (y <= 0)
    {
        // This is our base case.
        // We may not recurse here.
        result = 1;
    }
    else
    {
        // Here is the recursive case.
        result = x * power(x,y-1);
    }
    return result;
}

void main()
{
 int x,y;

 while (true)
 {
  cout << "Enter two numbers (0 0 to quit): ";
  cin >> x;
  cin >> y;

  if ((x == 0) && (y == 0))
   // user entered 0 0, so we quit.
   return;

  cout << x << "^" << y << " = "
    << power(x,y) << endl;
 }
}

Compile it, run it, understand it.

5.  Discussion of the Fibonacci Function:  fibonacci(n)

There is a useful sequence in mathematics called the Fibonacci sequence.  The first number is 1, and the second number is also 1.  After that, each number is simply the sum of the previous two numbers.  This results in the following sequence:

Fibonacci Sequence:  1, 1, 2, 3, 5, 8, 13, 21, 34,...
The Fibonacci function, fibonacci(n), returns the nth fibonacci number.  So:
fibonacci(0) = 1,
fibonacci(1) = 1,
fibonacci(2) = 2,
fibonacci(3) = 3,
fibonacci(4) = 5,
fibonacci(5) = 8,
fibonacci(6) = 13,
fibonacci(7) = 21,
...
This function is very naturally defined in a recursive manner as follows:
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
Of course, you also need to define a base case, lest you recurse infinitely, but that is left to you in the problem below.

6.  Write the functions iterativeFibonacci() and recursiveFibonacci() in the code below.  These should both compute the same thing, namely the Fibonacci function just described, but one should be iterative (using a for or while loop) whereas the other should be recursive.

#include <stdio.h>
#include <iostream.h>

int iterativeFibonacci(int n)
{
    // YOU WRITE THIS, PART 1 of 2
}

int recursiveFibonacci(int n)
{
    // YOU WRITE THIS, PART 2 of 2
}

void main()
{
 int n;

 while (true)
 {
  cout << "Enter a numbers (<0 to quit): ";
  cin >> n;

  if (n < 0)
   // user entered a negative #, so we quit.
   return;

  cout << "iterativeFibonacci(" << n << ") = "
    << iterativeFibonacci(n) << endl << endl;

  cout << "recursiveFibonacci(" << n << ") = "
    << recursiveFibonacci(n) << endl << endl;
 }
}

Good luck!

DK

See Course Home Page.