Profile

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);
}
PreviousRecursionNextRecursion-2

Last updated