APS 105 - Computer Fundamentals

Lab #6: Recursion

Fall 2000

You must submit this lab by 11:59pm Wednesday, November 1.

1. Objective

The objective of this lab is to become familiar with the use of recursion to solve problems.

2. Questions

Note: In each of the following questions, you will be asked to write a main() method as part of your class to demonstrate the methods you have written. It is important that this main() method does not expect user input. It should just contain a number of test cases that you design. You will not need Stdin.java for this lab and may not use it in the programs you submit.

1.

Write a recursive method public static void printTriangle(int n, char c) to print out a triangle of height n using character c. For example,

printTriangle(5,'*');

prints

*
**
***
****
*****

You may write other methods to be called by printTriangle(), but none of your methods may contain any loops. Do not add any additional output in your method. If n < 1 your method should not print anything. Make your method part of a class named Ptriangle. Write a main() method for Ptriangle to demonstrate the use of printTriangle().

2.

Write a recursive method public static void printOpenTriangle(int n, char c) that behaves in a similar manner to printTriangle, but

printOpenTriangle(5,'*');

prints

*
**
* *
*  *
*   *

Include it in a class named POtriangle, and include a main() method that demonstrates the use of printOpenTriangle().

3.

Write a recursive method

public static int sumDigits(int n)

that sums the digits of n and returns the sum. For example,

sumDigits(12345);

would return 15 (= 1 + 2 + 3 + 4 + 5). You may assume n > 0. Include your method in a class named Digits. Write a main() method for this class to demonstrate the use of your method.

4.

Write a recursive method

public static void printReverseDigits(int n, int base)

that prints the digits of n in reverse order using base base numbers. For example,

printReverseDigits(12345,10);

would print

54321

and

printReverseDigits(6,2);

would print

011

You may assume n >= 0 and 16 >= base >= 2. If base > 10 you are to use the letter 'A' to represent 10, 'B' to represent 11, 'C' to represent 12, ..., and 'F' to represent 15. Your method need not worry about advancing to a new line after the digits are printed. Include your method in a class named Pdigits, and include a main() method that demonstrates the use of your method.

Note: Since some people have expressed concern about ``number bases'', here is some basic information.

Every integer x can be expressed in terms of a base b via the following relation:

$$x = c_0b^0 + c_1b^1 + c_2b^2 + \ldots + c_nb^n$$

where the c_i are integer coefficients which may be zero or not. For example,

$$542 = 2\times 10^0 + 4\times 10^1 + 5\times 10^2\;.$$

Any x can be written in terms of different bases, for example,

$$542 = 6\times 8^0 + 3\times 8^1 + 0\times 8^2 + 1\times 8^3$$

and

$$542 = 0\times 2^0 + 1\times 2^1 + 1\times 2^2 + 1\times 2^3 +... ...5 + 0\times 2^6 + 0\times 2^7 + 0\times 2^8 + 1\times 2^9 \;.$$

Note that the coefficients c_i always have magnitude in the range $0\ldots (b-1)$. How to determine the coefficients? Let's look at the example where x = 542 and b = 10. Observe that $542 \;{\rm mod}\; 10 = 2$, and $542 \;{\rm div}\; 10 = 54$ and $54 \;{\rm mod}\; 10 = 4$, and so on.

5.

A polynomial of the form

$$p(x) = a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$$

can be evaluated efficiently using Horner's rule. This rule avoids explicit computation of the xⁱ terms as follows:

$$p(x) = a_0 + x(a_1 + x(a_2 + x( \ldots (a_{n-1} + xa_n) \ldots ))) \;.$$

Complete the definition of the recursive method horner with header

public static double horner(double [] a, double x, int i)

where the first parameter is an array of coefficients of the polynomial, the second is the value of x at which the polynomial is to be evaluated, and the third is an index that you should use to keep track of your recursion. You may assume that, when first called, the value of i is zero. Include this method in a class named Poly, and write a main() method to demonstrate its use.

3. What To Submit

You should submit the following files: Ptriangle.java, POtriangle.java, Digits.java, Pdigits.java and Poly.java. Do not submit Stdin.java, since none of your main() methods will require it.

4. Frequently Asked Questions About Lab 6

1.

For printTriangle is it ok if the designated methods are not recursive, but the helper methods are?
Yes. Just make sure that no loops are used. This answer also applies to printOpenTriangle.

2.

In part2 of Lab6, do I have to write a recursive method? b/c it doesn't mention that we need to write a recursive in the web site.
Yes.

3.

In part3, can I convert the int to a string, then use charAt() to get the number and finally convert it back to integer by using Integer.parseInt()?
No.

4.

For Lab 6, can I use the Integer class ?
No, it hasn't been taught.

5.

for part 4, must we reverse the digits of the base-10 integer first, then convert each base-10 digit to the appropriate base or must we first convert the base-10 integer to the appropriate base, then reverse the produced digits?
Convert, then reverse. If you think about it, you can do it all in one step via recursion.

6.

Can we use global variable for part 3?
No. You may not use global variables for any part of lab 6.

7.

In parts 1 and 2 of lab 6, are we allowed to call methods other than printTriangle() in main?
Assuming you mean "can we call our 'helper' methods?", the answer is 'No'. You may of course call methods like System.out.println().

8.

May we use `helper' methods for parts other than 1 & 2?
You may write a helper method to convert integers to digits $0\ldots 9,$ A ...F for Part 4, but no other helper methods.