HELPCLICK

Introduction to Programming CS1325

Assignment #6 – Recursion

Assignment #6 – Recursion

Introduction

Your sixth programming assignment will consist of two C programs. Your programs should

compile correctly and produce the specified output.

Please note that your program should comply with the commenting and formatting rules we

discussed in class. Those formatting requirements have now been updated to include variable

declarations and comment headers for functions. Please see the descriptive file on eLearning for

details.

Program 1 – Some General Recursive Algorithms

As we discussed in class, recursion is a very useful programming technique in which a function

makes a call to itself. Such a call is described as a “recursive function call.” Recursion can be

applied successfully to any problem in which the overall solution can be calculated from smaller

portions of the original problem. Although it incurs extra overhead in terms of time and

memory, recursion’s main advantage is that it can often vastly simplify the code. The following

examples will illustrate this.

For this assignment, let’s write recursive functions that solve three different problems:

1) Determining if a string is a palindrome or not. 2) Printing the characters of a string backwards instead of forwards. 3) Calculating the Greatest Common Divisor (GCD) of two integers. 4) Recursive Linear Search

All of these problems should be solved by a separate recursive function. You can determine

what the prototypes should be. In all cases, analyze the problem space for two characteristics:

(a) what the base case should be, and (b) how a larger problem can be solved by making

recursive calls to smaller, but similar problems. That will tell you how to set up the selection

logic statement that is necessary in a recursive function.

In general, your program should do the following:

1) For Problems (1) and (2) above, ask the user to input a character string. For Problem (1), determine whether the string is a palindrome or not by using a recursive function and

report the result to the user. For Problem (2), print the string in reverse (also by using a

recursive function).

CS1325 – Introduction to Programming page: 2

2) For Problem (3), ask the user to enter two integers. Determine the GCD by using a recursive function and report the result to the user.

An example run of the program might look like this:

Please enter a character string: abdef

The string “abdef” is not a palindrome.

The string “abdef” backwards is “fedba”.

Please enter two integers: 10 25

The GCD of 10 and 25 is 5.

3) For Problem (4), use the 150 element data array we used in HW 5. You may initialize the array with an initialization list as we did in HW 5. As described below, at the

minimum test the function on the numbers 71, 2400, 1988, and 2567. The first three are

in the array and the last one is not. (Note that both the first and last element of the array

are included in the test set. This is very good from a program testing viewpoint.)

Some programming notes that will help:

1) Palindromes

A palindrome is a string that reads the same forwards or backwards. For example, the

word “radar” is a palindrome, while the word “apple” is not (“apple”  “elppa”). Note

that palindromes do not have to be meaningful words. For example, the string

“abcddcba” is also a palindrome. Finally, palindromes can be of even or odd length.

Your function should be able to handle both.

Any palindrome must begin and end with the same character. In addition, the interior

portion of a palindrome, that is, the part of the string that omits the first and last

character, must also be a palindrome. This is the portion of the string on which your

function can make a recursive call.

Write your function to return 1 if the string is a palindrome, and 0 if it is not. In this

problem, let us treat lower and upper case letters as distinct characters. (Therefore, the

string “ABa” would not be a palindrome.)

2) Printing a character string backwards

For this problem, your function does not need to return a value. Just have it recursively

print the characters of a string backwards.

(What change would cause the recursive function print the characters forwards?)

CS1325 – Introduction to Programming page: 3

3) Greatest Common Divisor

The Greatest Common Divisor of two integers is the largest integer that evenly divides

them both. For example, the GCD of 16 and 24 is 8, the GCD of 18 and 24 is 6, and the

GCD of 17 and 24 is 1. Note that the GCD does not have to be a prime.

The recursive formulation for this problem is given in Problem 5.39 on page 211 of our

book. In general, the GCD of integers x and y is defined recursively as follows: If y is

equal to 0, then GCD(x,y) is x; otherwise, GCD (x,y) is GCD (y, x%y).

Have your function return the GCD of x and y as an int.

4) Recursive Linear Search

Implement a recursive linear search algorithm as we discussed in class. You may use the

data array that we used in the previous homework (i.e., 150 random numbers between 0

and 3000). Include a (global) counter that counts the number of recursive calls made.

Ask the user for the key to search for in each case, and report back whether the number

was found or not and the number of function calls that were made. Verify your algorithm

on the following five numbers at least: 71 (position 0, 1 function call), 2400 (position

149, 150 function calls), 1988 (position 125, 126 function calls), 2567 (not found, 151

function calls).

Here are some sample runs:

Please enter the search key: 2574

FOUND: Key 2574 was located at position 134. # of function calls: 135

Please enter the search key: 2567

NOT FOUND: Key 2567 was not located in the data set.

Do you see a relationship between the number of function calls and the index position of

the element (if it is found)?

5) 5 Point Bonus (Challenging)

Re-implement the Recursive Linear Search algorithm, but this time use a divide and

conquer approach similar to the Binary Search. In general terms, do the following:

a) Determine the mid-point of the current array. b) Recursively call the function on both the left and right halves of the array. c) Compare the results from the two halves and report back the larger of the two as

the answer. (Note that -1 indicates the number was not found, whereas, if it was

found, the return value will be an index >= 0.)

CS1325 – Introduction to Programming page: 4

In this function, also include a counter that counts the number of function calls. How

does this number compare to the number produced by the previous recursive linear search

algorithm? Why is this number so much larger?

Program 2 – Towers of Hanoi

A complete description of the Towers of Hanoi problem is found in problem 5.36, p. 208 of the

Deitel text book (8 th

edition). A scan of that problem will be provided below for those who don’t

have the book.

Your task: Implement the Towers of Hanoi solution using the recursive method described in the

book. As the book suggests, you should use a recursive function with four input parameters.

Have your program get the following information from the user:

1) The number of disks to be moved. 2) The peg the disks are currently on, i.e., the “current” peg. 3) The peg to which we wish to move the disks, i.e., the “target” peg.

Your program will thereafter assume that the third peg, i.e., the one not mentioned in steps (2)

and (3) above, will be used as the temporary storage peg. (Your program needs to calculate this.)

Test your program on several values for the number of pegs to be moved, for example: 3, 5, 8,

and 10. As described in the book, your program should print out the exact set of instructions

necessary to move the selected number of disks from the current peg to the target peg.

In addition to the above, include a counter that counts the number of moves printed. Include a

report at the end that reveals this number.

For some sample runs:

Now moving 3 disks from Peg 1 to Peg 3:

Move #: 1, Move: 1 -> 3

Move #: 2, Move: 1 -> 2

Move #: 3, Move: 3 -> 2

Move #: 4, Move: 1 -> 3

Move #: 5, Move: 2 -> 1

Move #: 6, Move: 2 -> 3

Move #: 7, Move: 1 -> 3

Move Count = 7

Now moving 4 disks from Peg 2 to Peg 1:

Move #: 1, Move: 2 -> 3

Move #: 2, Move: 2 -> 1

Move #: 3, Move: 3 -> 1

Move #: 4, Move: 2 -> 3

CS1325 – Introduction to Programming page: 5

Move #: 5, Move: 1 -> 2

Move #: 6, Move: 1 -> 3

Move #: 7, Move: 2 -> 3

Move #: 8, Move: 2 -> 1

Move #: 9, Move: 3 -> 1

Move #: 10, Move: 3 -> 2

Move #: 11, Move: 1 -> 2

Move #: 12, Move: 3 -> 1

Move #: 13, Move: 2 -> 3

Move #: 14, Move: 2 -> 1

Move #: 15, Move: 3 -> 1

Move Count = 15

Programming Notes:

1) Make sure your recursive algorithm has a way to stop. The base case occurs when the number of disks moved == 1 and is described in the book.

2) For 5 bonus points, can you see a relationship between the number of disks that need to be moved and the number of moves it takes to move them? What formula would you use

to calculate the number of moves necessary for “n” disks?

Deliverables

Please turn in your source code files for both problems.

Problem Scan

CS1325 – Introduction to Programming page: 6