Description
Recursion: Paper Exercise 1
Q1:What do the following two programs print?
Q2: What does xMethod in each program do when
called with posi?ve integer as input?
(answer in plain English)
public class Lab11Ex1a{
public sta?c void main(String[] args) {
xMethod(5);
}
public sta?c void xMethod(int n) {
if (n > 0) {
System.out.print(n + ” “);
xMethod(n – 1);
}
}
}
public class LabEx1b{
public sta?c void main(String[] args) {
xMethod(5);
}
public sta?c void xMethod(int n) {
if (n > 0) {
xMethod(n – 1);
System.out.print(n + ” “);
}
}
}
1
2
• Q1: What does the following program print?
• Q2: What does xMethod do given positive integer as input (answer in plain English)?
public class Lab11Ex2{
public static void main(String[] args){
int result = xMethod(4);
System.out.println(“xMethod returned ” + result);
}
public static int xMethod(int n) {
if (n == 1)
return 1;
else
return n + xMethod(n – 1);
}
}
• Q3: What would happen if we made xMethod(-3) call in the main, instead of xMethod(5)?
Recursion: Paper Excercise 2
3
• Q1: What does the following program print?
• Q2: What does xMethod do, given positive integer as input (answer in plain English)?
public class Lab11Ex3
{
public sta?c void main(String[] args) {
xMethod(7254);
}
public sta?c void xMethod(int n) {
if (n > 0) { System.out.print(n % 10);
xMethod(n / 10);
}
}
}
Recursion: Paper Excercise 3
4
Q1: What does the following program print?
Q2: What does xMethod do (answer in plain English)?
public class Lab11Ex4 {
public sta?c void main(String[] args) {
int[] list = {2, 7, -11};
System.out.println(xMethod(list, list.length-1));
}
public sta?c int xMethod(int[] list, int high) {
if (high == 0) {
return list[0];
}
else {
int tmp=xMethod(list, high – 1);
if (tmp>list[high])
return tmp;
else
return list[high];
}
}
}
Recursion: Paper Exercise 4
5
Recursion: Paper Study
• Open file SumProd.java
It contains contains 2 methods that both compute the
sum: 1+2+3 …+n. One computes it in a way that you
have seen before (called, itera?ve way), and the other
in recursive way.
Similarly the program contains 2 methods that both
compute the product 1*2*3…*n (thus they compute
n! ) in itera?ve and factorial way.
Study with TAs and understand well all these 4 solu?ons.
6
Recursion: Programming Exercise 1
• Write a recursive method, called m, that computes
the following series:
• In the main method, write a test program that displays
m(i) for i = 1, 2, . . . , 10.
7
Recursion: Programming Exercise 2
• Write a recursive method, called countDigits, that
counts the number of digits in a given posi?ve
integer n.
• Open the file NumberOfDigitsStudents.java and
program your solu?on in the clearly indicated
spaces.
8
Recursion: Programming Exercise 3
• A string is a palindrome if it reads the same from the
lee and from the right. For example, word “kayak” is
a palindrome, so is a name “Anna”, so is a word “a”.
Word “uncle” is not a palindrome.
• Write a recursive method, called isPalindrome, that
returns true if the input string is a palindrome and
otherwise returns false. Test your method.
• No?ce: a word of length n is a palindrom if 1st and nth
lejer are the same, AND 2nd and (n-1)st are the same,
and so on … un?l we get to the “middle” of the word.
9
Checking if a string is a palindrome can be divided into
two subproblems:
1. Check if the 1st and the last character in the string are
the same
2. Ignore the two end characters and check if the rest
of the substring is a palindrome.
No?ce that the 2nd subproblem is the same as the
original problem but smaller in size.
Useful string methods: length(), charAt() and substring()
Idea/Strategy
10
11
12
Recursion: Extra Programming
Exercise
• Write a recursive method, called checkSorted,
that checks if the given array of integers is in
sorted order (from smallest to largest)
• TAs will give you hints/overview of the algorithm
• Open the file ArraySortedStudents.java and
program your solu?on in the clearly indicated
spaces.
More on Strings: String vs. char[]
• Similari?es:
– both are collec?ons of characters
– both indexed from 0 up to length – 1
– both are reference variables
• no == comparison!
String vs. char[]
• Differences:
– Access of single character: str.charAt(i) vs array[i]
– Strings cannot be modified internally once they are created
• No equivalent of array[i] = ‘x’
– String variables can be assigned constant strings where using new is
op?onal
String str;
str = “abc”;
str = new String(“def” );
– Most opera?ons on Strings are done with methods
array.length // not a method call; no ( )
str.length( ) // method call; ( ) required
Conversions: String ↔ char[]
char[] array;
char[] array2;
…
// Create String from array
String str = new String( array );
// Create array from String
array2 = str.toCharArray( );
Common Methods of String
• Review the various methods available in the
String class:
hIp://java.sun.com/javase/6/docs/api/java/lang/String.html
• charAt(…), indexOf(…), length(…)
• toCharArray(…)
• equals(…), compareTo(…)
• concat(…), substring(…),
• toLowerCase(…), toUpperCase(…)
• …