CS 101 (Fall 2000)
Quiz 4: Recursion

Quiz Posted
(Thursdays)
Given in class
(Thursdays)
21 Sep 28 Sep

Information about quizzes:

The questions are intended to be straightforward. If you keep up with the material in the class, almost no preparation may be necessary. The Collaboration Policy allows you to study in groups for the quizzes, but you are on your own when you take the quiz.

You will fare better on the quiz if you try working the problems before looking at the solutions. If you don't understand the question or its answer, please get help.

Directions: Study the following recursive procedures and answer the questions that follow. Do these practice exercises on paper. Do not type them into a computer. You'll learn much more doing them by hand.

int factorial(int n) {
   if (n <= 1)
      return 1;
   else
      return (n * factorial(n-1));
}


int sum1toN(int n) {
   if (n < 1)
      return 0;
   else
      return (n + sum1toN(n-1));
}


int add(int i, int j) { // assumes i >= 0
   if (i == 0)
      return j;
   else
      add(i-1, j+1);
}


int fib(int n) {  // assumes n >= 0
   if (n <= 1)
      return n;
   else
      return (fib(n-1) + fib(n-2));
}

  1. Identify the termination conditions (and resulting base case return values) in each of the above recursive procedures.

  2. Identify the recursive calls in each of the above procedures.

  3. Using the substitution model, show all the recursive calls and final result in the execution of factorial(5). For this same computation, draw the execution stack as it would look just before returning from factorial(1), the last recursive call.

  4. Using the substitution model, show all the recursive calls and final result in the execution of sum1toN(5).

  5. Using the data flow model, show all the recursive calls and final result in the execution of add(5,9). For this same computation, draw the execution stack as it would look just before returning from add(0,14), the last recursive call.

  6. Using the data flow model, show all the recursive calls and final result in the execution of fib(5).

[ solution ]


Last modified 22:12:21 CST 31 January 1999 by Ron K. Cytron