# CS 373 Laboratory 8: Recursion

###### (Author: Steve Vegdahl: vegdahl@up.edu)

Lab date: Thursday, 30 October 1997
Writeup due: Thursday, 6 November 1997

The purpose of this lab is to give you additional experience with recursion. You will be examining eight recursive functions:

• factorial (done for you as an example)
• binary search
• greatest common divisor
• test string for being a palindrome
• sorting
• multiplication
• print number in any base
• substring test

For each function, you will be asked to

• identify the base case(s) and recursive case(s), describing them in English.
• argue that the function will terminate.
• "walk through" the program on a handful of examples, making a hypotheses about the results of each recursive call, if any.
• test your "walk-through" hypotheses using the debugger.

## Prelab

Examine the attached programs. Attempt to understand how/why each of them works.

There is nothing to turn in for the prelab, but you can get a head start by beginning on the "paper" portion of the lab before our lab time.

The following uses fact.C as an example of what I expect you to do for the other algorithms. Become familiar with fact.C, and think about how you would answer similar questions for the other algorithms

Factorial: fact.C

Examine the fact function in fact.C.

0a. Describe in English the base case(s):
 The base case is when our function is called with an argument that is less than or equal to zero.

0b. Describe in English the recursive case(s):
 The recursive case is when our function is called with an argument that is greater than zero.

0c. Sketch a proof that the function will always terminate:
 The algorithm terminates immediately in the base case. In the recursive case, the recursive call is always made on a number that is one less than the argument.  Since we hit the base case when N is less than or equal to zero, there is no number, N, no matter how large, that will not become zero (or less) when decremented a sufficient number of times.

0d. Describe the execution of the top-level calls:

• fact(5)  5 is greater than zero, so we have the recursive case.  The recursive call to 4 yields the value 24.  This is multiplied by 5, giving a result of 120.
• fact(0)  An argument of zero gives us our base case, which immediately returns the value 1.

0e. Predict the result returned by a call to fact(7).
 fact(7) should return the result 5040 (i.e., 1*2*3*4*5*6*7).

0f. Predict for 0e the number of calls to the recursive function that are active when a base case is first encountered; if there is more than one base case, predict which base case will be the first to be encountered.
 There should be a total of 8 active calls to fact when the first base case is encountered (one for each of the values 7 down through 0). There is only one base case in this function (n <= 0), so it is the one that is hit.

0g. Run the debugger on the fact executable to confirm your answers to 0d, 0e, and 0f above. (The up and down buttons, the where button, and the Inspector selection of the Stack menu may be useful in confirming 0f.) List any differences between your predictions and the actual results:
 There are therefore no differences between the predictions and the actual behavior.

## Laboratory

Setup

Create a directory (e.g., lab8) within your directory structure. Copy all the files from the sources directory to this directory. Perform a "make" to build the executables.

Binary search: binSearch.C

Examine the binarySearch function in binSearch.C.

1a. Describe in English the base case(s):

1b. Describe in English the recursive case(s):

1c. Sketch a proof that the function will always terminate:

1d. Describe the execution of the top-level calls:

• binarySearch(27, testArray, testArray+sizeof(testArray)/sizeof(*testArray)-1), where testArray the one defined in 'main'.
• binarySearch(59, testArray, testArray+sizeof(testArray)/sizeof(*testArray)-1), where testArray the one defined in 'main'.

1e. Predict the result returned by a call to binarySearch(12, testArray, testArray+sizeof(testArray)/sizeof(*testArray)-1).

1f. Predict for 1e the number of calls to the recursive function that are active when a base case is first encountered; if there is more than one base case, predict which base case will be the first to be encountered.

1g. Run the debugger on the binSearch executable to confirm your answers to 1d, 1e, and 1f above. (The up and down buttons, the where button, and the Inspector selection of the Stack menu may be useful in confirming 1f.) List any differences between your predictions and the actual results:

Greatest common divisor: gcd.C

Examine the gcd function in gcd.C.

2a. Describe in English the base case(s):

2b. Describe in English the recursive case(s):

2c. Sketch a proof that the function will always terminate:

2d. Describe the execution of the top-level calls:

• gcd(24, 8)
• gcd(85, 20)

2e. Predict the result returned by a call to gcd(18, 45).

2f. Predict for 2e the number of calls to the recursive function that are active when a base case is first encountered; if there is more than one base case, predict which base case will be the first to be encountered.

2g. Run the debugger on the gcd executable to confirm your answers to 2d, 2e, and 2f above. (The up and down buttons, the where button, and the Inspector selection of the Stack menu may be useful in confirming 2f.) List any differences between your predictions and the actual results:

Palindrome test: palindrome.C

Examine the isPalindrome function in palindrome.C.

3a. Describe in English the base case(s):

3b. Describe in English the recursive case(s):

3c. Sketch a proof that the function will always terminate:

3d. Describe the execution of the top-level calls:

• isPalindrome(str, str+6), where str is the string "abcdcba".
• isPalindrome(str, str+6), where str is the string "abcdcbb".

3e. Predict the result returned by a call to isPalindrome(str, str+9), where str is the string "banannanab".

3f. Predict for 3e the number of calls to the recursive function that are active when a base case is first encountered; if there is more than one base case, predict which base case will be the first to be encountered.

3g. Run the debugger on the isPalindrome executable to confirm your answers to 3d, 3e, and 3f above. (The up and down buttons, the where button, and the Inspector selection of the Stack menu may be useful in confirming 3f.) List any differences between your predictions and the actual results:

Insertion sort: isort.C

Examine the sort function in isort.C.

4a. Describe in English the base case(s):

4b. Describe in English the recursive case(s):

4c. Sketch a proof that the function will always terminate:

4d. Describe the execution of the top-level call:

• sort(testArray, sizeof(testArray)/sizeof(*testArray)), where testArray is the one defined in 'main'.

4e. Predict the effect of the call in 4d on the array testArray.

4f. Predict for 4e the number of calls to the recursive function sort that are active when a base case is first encountered; if there is more than one base case, predict which base case will be the first to be encountered.

4g. Run the debugger on the isort executable to confirm your answers to 4d, 4e, and 4f above. (The up and down buttons, the where button, and the Inspector selection of the Stack menu may be useful in confirming 4f.) List any differences between your predictions and the actual results:

Multiplication: multiply.C

Examine the multiply function in multiply.C.

5a. Describe in English the base case(s):

5b. Describe in English the recursive case(s):

5c. Sketch a proof that the function will always terminate:

5d. Describe the execution of the top-level calls:

• multiply(0, 45)
• multiply(53, 21)

5e. Predict the result returned by a call to multiply(21, 41).

5f. Predict for 5e the number of calls to the recursive function that are active when a base case is first encountered; if there is more than one base case, predict which base case will be the first to be encountered.

5g. Run the debugger on the multiply executable to confirm your answers to 5d, 5e, and 5f above. (The up and down buttons, the where button, and the Inspector selection of the Stack menu may be useful in confirming 5f.) List any differences between your predictions and the actual results:

Number-printing: printNum.C

Examine the printNum function in printNum.C.

6a. Describe in English the base case(s):

6b. Describe in English the recursive case(s):

6c. Sketch a proof that the function will always terminate:

6d. Describe the execution of the top-level calls:

• printNum(cerr, 8, 10)
• printNum(cerr, 48, 10)

6e. Predict the output generated by the call printNum(cerr, 1302, 16).

6f. Predict for 6e the number of calls to the recursive function that are active when a base case is first encountered; if there is more than one base case, predict which base case will be the first to be encountered.

6g. Run the debugger on the printNum executable to confirm your answers to 6d, 6e, and 6f above. (The up and down buttons, the where button, and the Inspector selection of the Stack menu may be useful in confirming 6f.) List any differences between your predictions and the actual results:

Substring search: subString.C

Examine the containsString function in subString.C.

7a. Describe in English the base case(s):

7b. Describe in English the recursive case(s):

7c. Sketch a proof that the function will always terminate:

7d. Describe the execution of the top-level calls:

• containsString("abc", "");
• containsString("abc", "apples, bananas, and cranberries");

7e. Predict the result returned by a call to containsString("xy", "x is greater than y, right?").

7f. Predict for 7e the number of calls to the recursive function that are active when a base case is first encountered; if there is more than one base case, predict which base case will be the first to be encountered.

7g. Run the debugger on the subString executable to confirm your answers to 7d, 7e, and 7f above. (The up and down buttons, the where button, and the Inspector selection of the Stack menu may be useful in confirming 7f.) List any differences between your predictions and the actual results:

Handin

Hand in the paper copy of this lab with your answers on it.