2.6Recursion-Practice 1

이전 포스팅에서 배운 재귀 알고리즘을 연습해보자.

예시 1: reverse

Write a recursive function called reverse which accepts a string and returns a new string in reverse.

• 우선 Base Case(종료 조건)을 먼저 생각한다.
  • 언제 이 함수가 더 이상 자신을 호출하지 않아도 되는가?
  • 문자열이 1글자 또는 빈 문자열일때이다. 이 때는 문자열을 그대로 반환한다.
• 다음으로 재귀적으로 반복될 함수를 생각한다.
  • 문자열이 2글자일 때는 첫번째 문자를 떼서 뒤로 붙이는 것이다.
  • 문자열이 3글자일 때는 위의 과정을 했을때 한번 더 앞쪽 2글자 문자열에 대해 또 진행하면 된다.
  • ...

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

예시 2: isPalindrome

Write a recursive function called isPalindrome which returns true if the string passed to it is a palindrome (reads the same forward and backward). Otherwise it returns false.

• 우선 Base Case(종료 조건)을 먼저 생각한다.
  • 언제 이 함수가 더 이상 자신을 호출하지 않아도 되는가?
  • 문자열이 1글자 또는 2글자때이다. 1글자일 때는 늘 true이고, 2글자일 때는 첫번째와 두번째 글자의 비교를 반환하면 된다.
• 다음으로 재귀적으로 반복될 함수를 생각한다.
  • 문자열이 3글자일 때는 첫번째 문자와 끝 글자를 비교하고, true면 그 두 글자를 없애고 가운데 있는 글자가 1개이므로 true를 반환하고, false면 false를 반환한다.
  • 문자열이 4글자일 때는 3글자일때와 같이 가지만, 가운데 있는 글자가 2개이므로 닫시 첫번째 글자와 끝글자(2글자)의 비교를 반환한다.
  • ...

javascript
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;
}

나는 앞선 문제가 reverse다 보니 이렇게 풀었다. 재귀적으로 푸는게 답인데, 이 경우 reverse만 이용한 것이기 때문에 출제 의도를 빗나간 풀이다.

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

function isPalindrome(str){
    const originalStr = str;
    const reversedStr = reverse(str);
    return originalStr === reversedStr
}

예시 3: someRecursive

Write a recursive function called someRecursive which accepts an array and a callback. The function returns true if a single value in the array returns true when passed to the callback. Otherwise it returns false.

javascript
// 예시
const isOdd = val => val % 2 !== 0;

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

• 우선 Base Case(종료 조건)을 먼저 생각한다.
  • 언제 이 함수가 더 이상 자신을 호출하지 않아도 되는가?
  • callback의 결과로 하나라도 false가 있을때다.
• 다음으로 재귀적으로 반복될 함수를 생각한다.
  • 배열의 첫 요소에 대해 callback을 실행하고, true면 다음으로 넘어가고 false면 종료한다.
  • ...

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

예시 4: flatten

Write a recursive function called flatten which accepts an array of arrays and returns a new array with all values flattened.

• 우선 Base Case(종료 조건)을 먼저 생각한다.
  • 언제 이 함수가 더 이상 자신을 호출하지 않아도 되는가?
  • 배열의 모든 요소가 (더 이상) 배열이 아닐 때다.
• 다음으로 재귀적으로 반복될 함수를 생각한다.
  • 배열의 첫 요소에 대해 배열인지 확인하고, 아니면 넘어가고 맞으면 그 안에서 다시 배열을 푼다.
  • ...

javascript
function flatten(oldArr){
  // 이후 concat, push로 변형시키기 때문
  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;
}

---

🤠 개인 탐구

안 쓰다보면 헷갈리기 쉬운 배열 메소드들

정말 자주 본 내용들이지만 깜박하면 헷갈리는게 배열 메소드들인것 같다. 한번 더 정리해본다.

기능은 익숙하지만, 원본을 변경하는지 여부와 반환값이 다 달라 종종 헷갈린다. 반환값에 대해선 가장 자주 쓰일 값을 반환한다고 생각하면 편하다.

예를 들어, 요소를 추가하는 push()와 unshift()는 루프문 등에서 종종 쓰이기에 루프를 끝낼 조건으로 필요한 새 배열 길이가 반환된다. while(arr.push(x)) < 10식으로, 배열의 크기만큼 요소를 추가하고 다음 배열로 넘어간다거나 하는 fetching 사례를 생각해보면 쉽다.

반면, 요소를 제거하는 pop()과 shift()는 스택이나 큐에서 값을 빼서 해당 값으로 뭔가를 하는 경우가 많기 때문에 제거한 요소를 반환한다.

slice(start, end)는 지정한 인덱스 범위로 배열을 복사하고 원본 배열은 그대로 두는 것이기 때문에 복사한 배열을 반환해야 해당 데이터를 쓸 수 있다.

splice(start, deleteCount, ...items)는 원본 배열의 특정 위치에 있는 요소들을 변경하는 것이 목적이기 때문에 원본을 변환하는데, 그렇게 변환이 된 원본 값은 원본에 접근함으로 얻을 수 있지만 그렇게 해서 변환되어 없어진 값은 다른 방법으로 얻기가 어렵기 때문에 메소드 자체에서 반환한다.