<![CDATA[
CSE143 Simple Recursion Examples handout #12
// iterative method that produces an output line of exactly n stars
public void writeStars(int n) {
for (int i = 0; i < n; i++)
System.out.print("*");
System.out.println();
}
// recursive method that produces an output line of exactly n stars
public void writeStars2(int n) {
if (n == 0)
System.out.println();
else {
System.out.print("*");
writeStars2(n - 1);
}
}
// post: reads a file, writing the lines to System.out in reverse order
public void reverse(Scanner input) {
if (input.hasNextLine()) {
String line = input.nextLine();
reverse(input);
System.out.println(line);
}
}
// returns the integer obtained by replacing every digit of n with two of
// that digit. For example, stutter(348) returns 334488.
public int stutter(int n) {
if (n < 0)
return -stutter(-n);
else if (n < 10)
return n * 11;
else
return 100 * stutter(n / 10) + stutter(n % 10);
}
// writes the binary representation of n to System.out
public void writeBinary(int n) {
if (n < 0) {
System.out.print("-");
writeBinary(-n);
} else if (n < 2)
System.out.print(n);
else {
writeBinary(n / 2);
System.out.print(n % 2);
}
}
]]>
<![CDATA[
CSE143 Trace of Simple Recursion Examples
Below is a trace of the call writeStars2(3):
writeStars2(3); (n > 0, recursive case)
System.out.print("*");
writeStars2(2); (n > 0, recursive case)
System.out.print("*");
writeStars2(1); (n > 0, recursive case)
System.out.print("*");
writeStars2(0); (n == 0, base case)
System.out.println();
Below is a trace of the call Reverse(input) when the input file contains
"this"/"is"/"fun"/"no?" on separate lines:
reverse(input);
line = input.nextLine(); (line == "this", recursive)
reverse(input);
| line = input.nextLine(); (line == "is", recursive)
| reverse(input);
| | line = input.nextLine(); (line == "fun", recursive)
| | reverse(input);
| | | line = input.nextLine(); (line == "no?", recursive)
| | | reverse(input);
| | | | input.hasNextLine() returns false (base case)
| | | System.out.println(line); (output "no?")
| | System.out.println(line); (output "fun")
| System.out.println(line); (output "is")
System.out.println(line); (output "this")
Below is a trace of the call stutter(-348):
stutter(-348)
is < 0, so execute first branch
compute stutter(-n), which is stutter(348)
| not < 0, not < 10, so execute third branch
| compute stutter(34)
| | not < 0, not < 10, so execute third branch
| | compute stutter(3)
| | | not < 0, but is < 10, so execute second branch
| | | return n * 11 (33)
| | compute stutter(4)
| | | not < 0, but is < 10, so execute second branch
| | | return n * 11 (44)
| | return first * 100 + second (33 * 100 + 44 = 3344)
| compute stutter(8)
| | not < 0, but is < 10, so execute second branch
| | return n * 11 (88)
| return first * 100 + second (3344 * 100 + 88 = 334488)
return the negation of that result (-334488)
Below is a trace of the call writeBinary(-39):
writeBinary(-39); (n < 0, recursive case)
System.out.print("-");
writeBinary(39); (n >= 2, recursive case)
writeBinary(19); (n >= 2, recursive case)
| writeBinary(9); (n >= 2, recursive case)
| | writeBinary(4); (n >= 2, recursive case)
| | | writeBinary(2); (n >= 2, recursive case)
| | | | writeBinary(1); (n < 2, base case)
| | | | | System.out.print(n); (writes out 1)
| | | | System.out.print(n % 2); (writes out 0)
| | | System.out.print(n % 2); (writes out 0)
| | System.out.print(n % 2); (writes out 1)
| System.out.print(n % 2); (writes out 1)
System.out.print(n % 2); (writes out 1)
]]>