CSE143 Simple Recursion Examples handout #8 // 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); } }
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)
Stuart Reges