Homework 3: Recursion and stacks

Part 1. Practice with recursion.
Write short C++ functions to solve all of the following problems using a recursive approach. (It is acceptable to write separate “driver” and “helper” functions for each probably, such separation is not really needed in Part 1.) For Part 1, you are not required to use an object-oriented approach.
Place all of your solutions in a single file called hw3a.cpp. The main function of the file should demonstrate all of your solutions, by running some tests that you create and producing output that will be easy for the grader to understand.
Recursive multiplication. Write a function that uses recursion to compute m * n = m + m + … + m
where m and n are both nonnegative integers. The function should accept two arguments, m and n. The function should return the computed value as an int. Your final recursive function should not send any output to cout, except possibly to handle exceptions. (During debugging, of course, you are encouraged to use any print statements that help with code development.) Your main program should test this function using several values of m and n. In your tests, include cases that use m = 0 and n = 0.

Recursive power function.

Write a function that uses recursion to compute 𝒂𝒂𝒏𝒏. The function should accept two arguments, a (of type double) and n (a nonnegative integer). The function should return the computed value as a double. Your final recursive function should not send any output to cout, except possibly to handle exceptions. Your main function should test this function using a = 2.0 and exponent values n = 0 through 10. Test it also using a = 3.1416 and exponent values n
= 0 through 2. Finally, include at some tests with a = 0.0 and a = 1.0.

Recursive palindrome detection.

A palindrome is a string that is the same if the string is reversed.
Some examples are “ana”, “abba”, “racecar”, “pot top”, and “able was I ere I saw elba”. Write a function that uses recursion to detect palindromes. The function should accept one parameter (a string), and should return true if that string is a palindrome, and otherwise it should return false.
Your final recursive function should not send any output to cout, except possibly to handle exceptions. Your main function should test this function with the cases shown above, as well as with some nonpalindrome cases. (The writeBackward() example in Chapter 2 illustrates
some simple string manipulation that may be helpful.) For this problem, white-space characters should be considered as part of the string that is to be reversed.
Reversing a sequence using recursion. Write a function that accepts an array of strings, and uses a recursive approach to print the array in reverse order. Your final recursive function should send its output to cout, and should not return any value to main. Your function should not change the contents of the array that is passed to it. Before running thisrecursive function, your main function should accept the name of a text file as a command-line argument, and should use a loop to read strings from the specified text file until the end of the file is reached. You may assume that each line of the text file contains one string, and (for simplicity) you may assume that there are no white-2 space characters in any of the strings. Your main program should place the strings into an array
in the same order as they appear in the file. To decide the size of your array, you may assume that
the input file will not contain more than 50 strings.
Notice that only the last case of these problems requires the use of command-line arguments and of file I/O. So, you can write one main function that tests all of the recursive functions that are described for Part 1.

Part 2. Practice with stacks.
For Part 2, you must follow object-oriented principles and you must use a stack ADT, which is the topic of chapters 6 and 7 in the textbook. You may use any of the stack ADT versions that appear in the textbook. Place your client code (with the main function) in a file called hw3b.cpp.
For Part 2, write a program that uses a stack to accomplish the same “reversal” task as the last recursive function described in Part 1. (Your code in Part 2 should be iterative, not recursive.)
Once again, your main function should accept the name of a text file as a command-line argument, and should iteratively read strings from the specified text file until the file is empty. You may assume that each line of the text file contains one string, and you may assume that there are no white-space characters in any of the strings. Instead of placing strings into an array, however, your main program should push each string onto a stack as soon as the string has been read from the input file. Then your program should perform whatever actions are needed to send the strings to cout, such that the strings are output in the opposite order that they are appear in the input file.
For example, it is acceptable to pop items from your stack.
Exception handling: For parts 1 and 2, your code should check for certain conditions, and should
generate a simple error message to cout if detected:
1. The expected number of arguments are not given on the command line.
2. A specified input file does not exist.
3. Methods such as push and pop, which return a Boolean success code, do not complete
successfully.
Instead of sending a simple error message to cout, you are welcome to explore more sophisticated techniques for handling exceptions, as described in Interlude C3 of the textbook.
What to hand in: Place all of your C++ files in a ZIP archive with file name hw3_name.zip,
where name is your family name. Upload that ZIP file to Canvas. As usual, be careful to upload the correct files. For Part 1, only the file hw3a.cpp is required. For Part 2, you should submit hw3b.cpp along with all of the stack-related files that you have used.
Partial credit: If your program does not run correctly, also turn in a written description (Word or
PDF or TXT file) that describes 1) the problems you encountered, 2) what parts of your programs
work correctly, and 3) suggestions to the grader as to how your program may be tested for partial
credit consideration. If your program runs correctly, you do not need to turn in such a file.
Grading: The assignment will be graded out of a maximum of 100 points: 80 points depend on
correct program operation, and the remaining 20 points are based on programming style. Please
refer to the style guidelines that are posted at Canvas.