Lab 5: Recursion

CS 305 Lab 5: Recursion

The purpose of this lab is to give you additional experience with recursion, a topic
that was introduced in CS 203. You will be examining and completing the following
recursive functions:
 Testing a string for being a palindrome.
 Multiplication, using the Russian Peasant's Algorithm.
 Print a number in a given base.
Recall that recursive functions are written such that recursive calls of the function
lead toward base case(s). For each of the recursive functions in this lab, either the
base case or the recursive case (or both) is incomplete. You job will be to complete
the function and then examine the stack upon execution.
This lab has a total of 100 possible points (30 points from pre-lab and 70 points
from lab).
Sit with your assigned partner.
Objectives
Upon completion of the laboratory exercise, you will be able to do the following:
 Identify the base case(s) and recursive case(s) for the recursive functions
listed above.
 Understand why each function terminates.
 Use the debugger to examine the stack for recursive function calls.
Part 1: Logging in (choose one person)
1. Follow the procedure from prior labs to log in and open Mobaxterm:
2. Go into your cs305 directory. Make a new lab5 directory:
cd cs305
mkdir lab5
3. Get the lab5 files. Download starter_lab5.zip from moodle to your cs305
folder. Hopefully, you can see the zip file. To unzip it, type
unzip starter_lab5.zip
There should be three .c files.
Part 2: Palindrome test (palindrome.c) – Fix the recursive
case
1. Examine the is_palindrome function in palindrome.c. This function is supposed
to determine whether a string is a palindrome (i.e., whether it reads the same
backward as forward).
The function takes three parameters:
 a string
 the index in the string of the first character to be considered to be part of the
palindrome
 the index in the string of the last character in the string that is to be
considered part of the palindrome
2. The algorithm is as follows:
 base case #1 (already done): the first index is greater than or equal to
the last index. In this case we have a one-character or zero-character
string, which is a palindrome, so return 1.
 base case #2 (already done): the first index is less than the last index,
but the respective characters do not match. In this case return 0.
 recursive case (you need to do): the first index is less than the last
index, but the values at these character positions are equal. We have a
palindrome only if we get a palindrome after discarding the first and last
character of the string, so we can simply return the recursive call to
is_palindrome on this shorter string (shorter by 2 characters).
The algorithm should always terminate, because at each recursive call, we are
calling is_palindrome on a shorter substring.
3. Modify the recursive case so that it runs correctly. All other code should remain
the same. Compile and run the program.
gcc –g –o palindrome palindrome.c
./palindrome
Once you are confident it is working, use the debugger to run the program. Set a
breakpoint at the first line of code inside is_palindrome.
gdb palindrome
(gdb) run
Find the first line of code inside is_palindrome. Set a breakpoint there using the
break command. Then, use a combination of cont and info stack to view the
stack contents each time the breakpoint is hit (each time the function is recursively
called).
1. What are the call stack values for first_index and last_index when running the
program on input string “racecar” when the call stack is the largest?
first_index=____________________, last_index= ____________________
// continue list here
2. What is the call stack values when running the program on input string “barbed”?
first_index=____________________, last_index= ____________________
// continue list here
Checkpoint 1 [25 points]: Show your lab instructor/assistant your program
running with various strings and show your answers to the questions
above.
Part 3: Multiplication (multiply.c) – Fix the recursive case
(switch driver)
1. Examine the multiply function in multiply.c, which is intended to perform
multiplication using the Russian Peasant's Algorithm. This algorithm multiplies two
integers as follows:
 Base case: (already done) if the first integer is zero, then the result is zero.
 Base case: (already done) If one or both are negative numbers, then
recursively call multiply on the negated values.
 Recursive case: (you need to do) If the first integer is even, the result is the
result of recursively multiplying half of the first number by twice the second.
For example, you can multiply 24 times 7 by multiplying 12 (half of 24) by 14
(twice 7); this results in the value 168. If the first integer is odd, the result is
the result of recursively multiplying half of the first number (rounded down)
by twice the second, and then adding the second number to compensate for
the rounding down. For example, you can multiply 25 times 7 by multiplying
12 (half of 25) by 14 (twice 7), and then adding 7; this results in the value
175.
2. To see this algorithm in action, consider multiplying 13 times 20:
 13*20 is 6*40 + 20
o 6*40 is 3*80
 3*80 is 1*160 + 80
 1*160 is 0*320 + 160
 0*320 = 0 (base case)
 so 1*160 is 0 + 160 = 160
 so 3*80 is 160 + 80 = 240
o so 6*40 = 240
 so 13*30 is 240 + 20 = 260
Explain why this function will always terminate:
3. The starter file is written so that the base case is correct and some of the
recursive cases are correct, but the last recursive case is incomplete. Modify the
code so that the program runs correctly. All other code should remain the same.
Compile and run your program.
gcc –o multiply multiply.c
./multiply
Checkpoint 2 [25 points]: Show your lab instructor/assistant your program
running with various pairs of non-negative integers, including cases where
one or both are zero. Show your answer to the question above.
Part 4: Number-printing (print_num.c) – Fix the base cases
(switch driver)
1. Examine the print_num function in print_num.c. This function is intended to
print a number in any given base between 2 and 36. The main function reads an
integer and prints it in all bases between 2 and 36. The letters a through z are used
to represent the digits 10 through 35, respectively.
The function takes two arguments:
 the number to print
 the base to print the number in
2. Its intended operation is as follows:
 base case 1 (you need to do) the number is negative, print a - character,
and then recursively call the function with the negated number (which
becomes a positive number)
 base case 2 (you need to do): if the number is less than the base, print its
digit, using the digits array. Hint: be sure to print using formatting code %c
for character.
 recursive case (already done): if the number is greater than or equal to the
base
o recursively print the value of the number divided by the base. This
should print out all the digits except the last.
o recursively print the value of the number remaindered by the base.
This should print out the last digit.
3. For example, to print 173 in base 10:
 recursively print 173/10: this prints "17" by recursively calling print_num(17,
10)
 recursively print 173%10: this prints "3"
The result is that "173" is printed.
4. This function always terminates because:
 a negative value always results in a recursive call with a positive value. (We'll
ignore MIN_INT for now)
 a positive value always results in either the base case, or recursive calls with
smaller values.
5. Modify the base cases so that the program runs correctly. All other code should
remain the same. Compile and run your program.
gcc –g –o print_num print_num.c
./print_num
If you want the output to go to a file, use:
./print_num out.txt
(nothing will print to the screen, but you can still type the number here. Do less
out.txt to see the contents of the file)
Checkpoint 3 [20 points]: Show your lab instructor/assistant your code and
program running with 121.
Close Mobaxterm and any other applications. Log off the computer.
If any checkpoints are not finished, they are due in one week. You submit
screenshots, code files, and answers to questions electronically (on moodle).