Alogorithm - Recursion Problems

Recursion Problems

Reverse Problem

• 문자열을 받고, 그 문자열을 거꾸로 반환하는 회귀 함수 구현

Reverse Solution

• helper method recursion
  • inner helper function 접근 방법
    • slice 메소드를 사용해서 문자열을 자른다
    • 문자열을 거꾸로 변환해야하므로, index를 음수값으로 준다
    • 회귀 멈춘 조건(base)은 index가 문자열의 길이일 때로 정한다
    • 단항 연산자 ++를 사용하여 증가한 index 값을 회귀 함수의 매개변수에 넣어준다
    • 0은 음수도 0이므로 index가 0인 경우를 따로 고려한다

function reverse(str){
  let result = '';
  
  function helper(helperInput, index) {
      if (index === helperInput.length) {
          result += helperInput.slice(0, 1);
          return;
      }
      if (index === 0) {
          result += helperInput.slice(-1);
      } else {
       result += helperInput.slice(-index, -index + 1);   
      }
      helper(helperInput, ++index);
  }
  
  helper(str, 0);
  return result;
}

• pure recursion

function reverse(str){
  if (str.length <= 1) return str;
  return reverse(str.slice(1)) + str[0];
}

isPalindrome Problem

• 문자열이 앞과 뒤가 같을 경우 true를 다를 경우 false를 반환하는 회귀 함수 구현

isPalindrome Solution

• pure recursion 1
  • 접근방법
    • 첫번째 문자열과 마지막 문자열을 비교해서 다를 경우 false를 반환한다
    • 비교한 문자열을 제외한 문자열에서 다시 첫번째 문자열과 마지막 문자열을 비교한다
    • 문자열의 길이가 1 이하인 경우, 가운데 문자열을 제외하고 양옆의 문자열이 같으므로 true를 반환한다

function isPalindrome(str){
  if (str.length <= 1) {
      return true;
  }
  if (str[0] !== str[str.length -1]) {
      return false;
  }
  return isPalindrome(str.slice(1, -1))
}

• pure recursion 2

function isPalindrome(str){
    if(str.length === 1) return true;
    if(str.length === 2) return str[0] === str[1];
    if(str[0] === str.slice(-1)) return isPalindrome(str.slice(1,-1))
    return false;
}

someRecursive Problem

• array와 callback함수를 인자로 받고, array의 요소 중 하나라도 callback 함수의 반환값이 true라면 true를 반환하고 그게 아니라면 false를 반환하는 회귀 함수 구현

someRecursive Solution

• pure recursion
  • 접근방법
    • 배열의 첫번째 요소의 callback 함수 반환값이 true라면 true를 반환해준다
    • slice 메소드를 사용하여 첫번째 요소를 제외한 배열을 만들고, 회귀 함수의 매개변수에 넣어준다
    • 배열의 길이가 0이면 false를 반환한다

// someRecursive([1,2,3,4], isOdd) // true
// someRecursive([4,6,8,9], isOdd) // true
// someRecursive([4,6,8], isOdd) // false
// someRecursive([4,6,8], val => val > 10); // false

function someRecursive(arr, callback){
  if (arr.length === 0) {
      return false;
  }
  if (callback(arr[0])) {
      return true;
  }
  return someRecursive(arr.slice(1), callback);
}

flatten Problem

• 중첩 배열을 인자로 받아서 배열 하나로 만들어서 반환하는 회귀 함수 구현

flatten Solution

• helper method recursion
  • inner function 접근방법
    • 배열의 첫번째 요소의 타입이 'object'인 경우, 배열의 첫번째 요소를 인자로 회귀 함수를 호출한다
    • 배열의 첫번째 요소의 타입이 'object'가 아닌 경우, outer function 스코프의 배열에 배열의 첫번째 요소를 넣어준다
    • 배열의 첫번째 요소를 제외한 나머지 배열을 인자로 회귀 함수를 호출한다
    • 배열의 길이가 0인 경우 함수를 종료한다

// flatten([1, 2, 3, [4, 5] ]) // [1, 2, 3, 4, 5]
// flatten([1, [2, [3, 4], [[5]]]]) // [1, 2, 3, 4, 5]

function flatten(arr){
    let result = [];
    
    function helper(helperInput) {
       if (helperInput.length === 0) {
        return;
        }
        if (typeof helperInput[0] === 'object') {
            helper(helperInput[0]);
        } else {
            result.push(helperInput[0]);
        }
        helper(helperInput.slice(1));
    }
    
    helper(arr);
    return result;
}

• pure recursion example

function flatten(oldArr) {
  let newArr = [];
  for (let i = 0; i < oldArr.length; i++) {
    if (Array.isArray(oldArr[i]) {
      newArr = newArr.concat(flatten(oldArr[i]));
    } else {
      newArr.push(oldArr[i]);
    }
  }
  return newArr;
}

capitalizeFirst Problem

• 문자열 배열을 인자로 받아서, 첫글자를 대문자로 변환한 문자열의 배열을 반환하는 회귀 함수 구현

capitalizeFirst Solution

• pure recursion 1

  • 접근 방법

    • 배열의 첫 번째 문자열을 변수에 저장한다 (배열 탐색 중복을 막기 위해서)
    • slice 메서드를 사용하여 문자열의 첫 글자와 나머지 글자들을 추출한다
    • toUpperCase 메서드를 사용하여 첫 글자를 대문자로 변환한다
    • 대문자로 변환된 첫 글자와 나머지 글자들을 더해서 변수에 할당한다
    • 변환된 문자열을 배열에 넣어준다
    • 첫번째 문자열을 제외한 배열을 인자로 받아서 회귀함수를 호출한다
    • concat 메서드를 사용하여 배열을 합친다

// capitalizeFirst(['car','taco','banana']); // ['Car','Taco','Banana']

function capitalizeFirst (arr) {
  let newArr = [];
  
  if (arr.length === 0) {
      return newArr;
  }
  const letter = arr[0];
  const capitalLetter = letter.slice(0,1).toUpperCase();
  const restLetter = letter.slice(1);
  const newLetter = capitalLetter + restLetter;
  newArr.push(newLetter);
  return newArr.concat(capitalizeFirst(arr.slice(1)));
}

• pure recursion 2

function capitalizeFirst (array) {
  if (array.length === 1) {
    return [array[0][0].toUpperCase() + array[0].substr(1)];
  }
  const res = capitalizeFirst(array.slice(0, -1));
  const string = array.slice(array.length - 1)[0][0].toUpperCase() + array.slice(array.length-1)[0].substr(1);
  res.push(string);
  return res;
}