Recursion-1
factorial
Question
Given n of 1 or more, return the factorial of n, which is n * (n-1) * (n-2) ... 1. Compute the result recursively (without loops).
public int factorial(int n) {
if (n == 1) return 1;
return n * factorial(n-1);
}
bunnyEars
public int bunnyEars(int bunnies) {
if (bunnies == 0) return 0;
if (bunnies == 1) return 2;
return 2 + bunnyEars(bunnies - 1);
}
fibonacci
public int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
bunnyEars2
public int bunnyEars2(int bunnies) {
if (bunnies == 0) return 0;
if (bunnies%2 == 1) return 2 + bunnyEars2(bunnies -1);
else return 3 + bunnyEars2(bunnies -1);
}
public int bunnyEars2(int bunnies) {
int bunnyType = bunnies%2;
int ears = 0;
if (bunnies == 0) return 0;
if (bunnyType == 1) ears = 2;
if (bunnyType == 0) ears = 3;
return ears + bunnyEars2(bunnies -1);
}
triangle
public int triangle(int rows) {
if (rows == 0) return 0;
if (rows == 1) return 1;
return rows + triangle(rows -1);
}
sumDigits
public int sumDigits(int n) {
if (n < 10) return n;
return sumDigits(n/10) + n%10;
}
count7
public int count7(int n) {
int cnt = 0;
if (n%10 == 7) cnt++;
if (n < 10) return cnt;
return count7(n/10) + cnt;
}
count8
public int count8(int n) {
if (n == 0) return 0;
if (n % 10 == 8) {
if ((n / 10) % 10 == 8) return 2 + count8(n/10);
return 1 + count8(n/10);
}
return count8(n/10);
}
powerN
public int powerN(int base, int n) {
if (n == 1) return base;
return base * powerN(base, n-1);
}
countX
public int countX(String str) {
if (str.length() == 0) return 0;
String s = str.substring(0, str.length() - 1);
Character c = str.charAt(str.length()-1);
if (c == 'x') return 1 + countX(s);
return countX(s);
}
countHi
public int countHi(String str) {
if (str.length() == 0 || str.length() == 1) return 0;
String s = str.substring(0, 2);
String after = str.substring(1, str.length());
if (s.equals("hi")) return 1 + countHi(after);
return countHi(after);
}
changeXY
public String changeXY(String str) {
if (str.length() == 0) return str;
Character c = str.charAt(0);
String after = str.substring(1, str.length());
if (c == 'x') c = 'y';
return c + changeXY(after);
}
changePi
pi이면 두 칸 건너뛰고
pi아니면 한 칸씩 건너뛰고
public String changePi(String str) {
if (str.length() == 0 || str.length() == 1) return str;
if (str.substring(0, 2).equals("pi"))
return 3.14 + changePi(str.substring(2, str.length()));
return str.charAt(0) + changePi(str.substring(1, str.length()));
}
noX
public String noX(String str) {
if (str.length() == 0) return "";
if (str.substring(0,1).equals("x"))
return noX(str.substring(1, str.length()));
return str.charAt(0) + noX(str.substring(1, str.length()));
}
아래 euquals('x') 부분에서 쌍따옴표가 아닌 ' ' 단일 따옴표로 하니까 에러가 났다.
public String noX(String str) {
if (str.length() == 0) return "";
if (str.substring(0,1).equals('x'))
return noX(str.substring(1, str.length()));
return str.charAt(0) + noX(str.substring(1, str.length()));
}
array6
public boolean array6(int[] nums, int index) {
if (nums.length == 0) return false;
if (nums[index] == 6) return true;
if (index + 1 == nums.length) return false;
return array6(nums, index +1);
}
array11
public int array11(int[] nums, int index) {
if (nums.length == 0) return 0;
if (index == nums.length) return 0;
if (nums[index] == 11) return 1 + array11(nums, index+1);
return array11(nums, index+1);
}
array220
처음에 문제 이해 잘못하였다.
내가 알아서 이해하지 말고 문제 요구사항을 꼼꼼히 읽자.
public boolean array220(int[] nums, int index) {
if (index >= nums.length - 1) return false;
if (nums[index]*10 == nums[index +1]) return true;
return array220(nums, index +1);
}
Reafactor
public boolean array220(int[] nums, int index) {
if(index >= nums.length - 1)
return false;
return nums[index+1] == 10 * nums[index] || array220(nums, index + 1);
}
allStar
public String allStar(String str) {
if (str.length() == 1 || str.length() == 0)
return str;
return str.charAt(0) + "*" + allStar(str.substring(1, str.length()));
}
pairStar
public String pairStar(String str) {
if (str.length() == 0 || str.length() == 1) return str;
if (str.charAt(0) == str.charAt(1))
return str.charAt(0) + "*" + pairStar(str.substring(1, str.length()));
return str.charAt(0) + pairStar(str.substring(1, str.length()));
}
endX
public String endX(String str) {
if (!str.contains("x")) return str;
if (str.length() == 1) return str;
String s = str.substring(0, 1);
if (s.equals("x")) return endX(str.substring(1, str.length())) + s;
return s + endX(str.substring(1, str.length()));
}
countPairs
public int countPairs(String str) {
// sliding window 같다.
if (str.length() < 3) return 0;
String s = str.substring(0, 3);
if (s.charAt(0) == s.charAt(2))
return 1 + countPairs(str.substring(1, str.length()));
return countPairs(str.substring(1, str.length()));
}
countAbc
public int countAbc(String str) {
// sliding window
if (str.length() < 3) return 0;
String s = str.substring(0, 3);
if (s.equals("abc") || s.equals("aba"))
return 1 + countAbc(str.substring(1, str.length()));
return countAbc(str.substring(1, str.length()));
}
count11
public int count11(String str) {
if (str.length() < 2) return 0;
if (str.substring(0, 2).equals("11"))
return 1 + count11(str.substring(2, str.length()));
return count11(str.substring(1, str.length()));
}
stringClean
public String stringClean(String str) {
if (str.length() < 2) return str;
if (str.charAt(0) == str.charAt(1))
return stringClean(str.substring(1, str.length()));
return str.charAt(0) + stringClean(str.substring(1, str.length()));
}
countHi2
public int countHi2(String str) {
if (str.length() < 2) return 0;
if (str.charAt(0) == 'x') {
if (str.length() >= 3 && str.substring(1, 3).equals("hi")) {
return countHi2(str.substring(2, str.length()));
}
}
if (str.substring(0, 2).equals("hi"))
return 1 + countHi2(str.substring(2, str.length()));
return countHi2(str.substring(1, str.length()));
}
parenBit
two pointer 같다고 처음에 생각했다.
public String parenBit(String str) {
if (!str.contains("(") || str.length() < 2) return "";
if (str.substring(0, 1).equals("(")) {
int i = str.indexOf(")");
return str.substring(0, i+1);
}
return parenBit(str.substring(1, str.length()));
}
nestParen
public boolean nestParen(String str) {
if (str.length() == 0) return true;
if (str.charAt(0) =='(') {
if (str.charAt(str.length() -1) == ')')
return nestParen(str.substring(1, str.length()-1));
return false;
} else {
return false;
}
}
strCount
public int strCount(String str, String sub) {
// sliding window
int strLen = str.length();
int subLen = sub.length();
if (strLen < subLen) return 0;
String s = str.substring(0, subLen);
if (s.equals(sub)) {
if (strLen == subLen) return 1;
return 1 + strCount(str.substring(subLen, strLen), sub);
}
return strCount(str.substring(1, strLen), sub);
}
strCopies
public boolean strCopies(String str, String sub, int n) {
int result = 0;
if (str.length() < sub.length()) {
if (n == 0) return true;
else return false;
}
String s = str.substring(0, sub.length());
if (s.equals(sub)) result++;
boolean before = strCopies(str.substring(1, str.length()), sub, n-result);
if (before) return true;
else return false;
}
코드를 아래와 같이 리팩토링 하였다.
public boolean strCopies(String str, String sub, int n) {
int result = 0;
if (str.length() < sub.length()) {
if (n == 0) return true;
else return false;
}
if (str.substring(0, sub.length()).equals(sub)) result++;
if (strCopies(str.substring(1, str.length()), sub, n-result)) return true;
else return false;
}
strDist
중복 허용 안했을 때 에러가 났다.
public int strDist(String str, String sub) {
int subLen = sub.length();
if (str.length() < sub.length()) {
return 0;
}
if (str.substring(0, subLen).equals(sub)) {
String left = str.substring(subLen, str.length());
if (str.length() == subLen) return subLen;
if (left.contains(sub)) {
// exist
int i = left.indexOf(sub);
return subLen + i + strDist(left.substring(i, left.length()), sub);
}
else return subLen;
}
return strDist(str.substring(1, str.length()), sub);
}
중복 허용해주니 에러가 나지 않았다. 중복 가능 여부도 꼼꼼히 확인하자.
public int strDist(String str, String sub) {
int subLen = sub.length();
if (str.length() < sub.length()) {
return 0;
}
if (str.substring(0, subLen).equals(sub)) {
String left = str.substring(1, str.length());
if (str.length() == subLen) return subLen;
if (left.contains(sub)) {
int i = left.indexOf(sub);
return 1 + i + strDist(left.substring(i, left.length()), sub);
}
else return subLen;
}
return strDist(str.substring(1, str.length()), sub);
}
Last updated