CIS 067 Section 1

Assignment Number 09-F2001

A Simple Recursion Problem

Reading: Read Chapter 12, Sections 12.1 – 12.3 in the Friedman/Koffman Text.

Problem (modifying the factorial function) We developed an algorithm for recursively computing the factorial n! of a non-negative integer n. For this assignment, you will implement this function and a driver program to test your function. A few changes may be needed along the way.

A. Add three new data items (integer variables):

  1. A call-by-value argument named level used to keep track of the current call level of the factorial function.

  2. A local variable named new_n which is used as the actual argument in the recursive call to factorial (the call that occurs inside the function). This variable is always set to be n-1 just before the recursive call:

    new_n = n – 1;
    … factorial (new_n);

  3. A local variable named value_returned which keeps track of the value returned by the function factorial each time it returns. The changes to the in-class function will look something like this:

new_n = n – 1;
value_returned = factorial (new_n);
return n * value_returned;

B. Next, insert print statements into your program as follows:

  1. At each entry to the factorial function (inside the function), display a line such as

    2. ~~~~~ Factorial function entered at level = ð

    where ð represents the value of level and is increased by one each time the function is entered (just prior to printing this line).

  2. Inside the function, each time a new value of new_n is computed print this value.

  3. Inside the function, each time a new value of value_returned is computed, display 3 blank lines followed by three additional lines:

We have now returned to level ð ;
The value_returned = m
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

C. Test your function with driver program that calls factorial with level = 0 and n = 4.

Turn In: E-mail your final program to the lab assistant.
Due Date: Friday noon, Dec. 7, 2001.