재귀함수 문제 풀이

재귀함수 문제 풀이 순서

 

1. 입출력값을 확인하고 시뮬레이션 해본다.

2. base case를 생각해본다.

3. recursive case를 생각해본다.

4. edge case를 정리한다.

5. 코드를 작성한다.

 

종료조건(base case): 적어도 하나의 무한반복에 빠지지 않는 경우 

재귀조건(recursive case):  종료조건을 만족시키지 못한 나머지 경우

---

재귀함수 문제 풀이 주의 사항

 

1. 의사코드로 시뮬레이션을 몇번 적어보는 것이 도움이 된다.

2. 의사코드로 정리를 잘 하는 것이 중요하다.

3. 재귀함수를 써야할 때 가장 효율적으로 쓰인걸 까 고민해봐야한다.(관련 개념: 빅오 표기법)

4. 때에 따라서 클로저를 재귀함수로 사용할 수도 있다.

5. 재귀함수의 리턴문이 함수를 호출하는 부분과 일반값을 처리하는 부분이 함께있다면,

적절한 변수명으로 할당한 뒤 적어주는 것이 좋다.

 

---

재귀함수 문제01

 

문제:

수(num)와 배열을 입력받아 차례대로 num개의 요소만 포함된 새로운 배열을 리턴해야 합니다.

 

입력:

인자1 : num	인자2 : arr
number 타입의 정수 (num >= 0)	임의의 요소를 갖는 배열

 

출력:

• 순차적으로 num 개의 요소로 구성된 배열을 리턴해야 합니다.

 

주의사항:

• 함수 take는 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).

 

입출력 예시:

let output = take(2, [1, -2, 1, 3]);
console.log(output); // --> [1, -2]

output = take(5, [1, -2, 1, 3]);
console.log(output); // --> [1, -2, 1, 3]

 

📝 이 문제는... 

처음 풀 때는 num만큼 빼는 것이 아니라 가져가는 것이기 때문에, 종료 시점을 어떻게 해야 할지 헷갈렸다.

두번째로 풀어 볼 땐 뭔가 더 효율적인 방식이 있지 않을까 고민하게 되었는데,

클로저를 이용하니 조금 더 효율적인 방식으로 풀 수 있었다.

그리고 레퍼런스 코드를 보니, 클로저를 쓰지 않고도 효율적인 방법이 있었다.

 

 

첫번째 풀이: 바보같은 재귀함수 사용법

function take(num, arr) {
  // 의사코드로 시뮬레이션 해보기
  //take(4, [-1, -2, 1, 2, 3, 4, 5]);
  //take(4, [-1, -2, 1, 2, 3, 4])
  //take(4, [-1, -2, 1, 2, 3])
  //take(4, [-1, -2, 1, 2]) => num과 arr.length가 같을 때 리턴 arr

  //exception case
  if(arr.length === 0) return []
  if(num > arr.length) return arr //뽑아내야 하는 갯수 num이 arr.length보다 클 경우 (take(3,[1,2]))
  
  //base case
  if(num === arr.length) return arr //뽑아내야 하는 갯수 num이 arr.length와 같을 경우
  
  //recursive case
  return take(num, arr.slice(0,arr.length-1)) //복사하고 맨 뒷 요소를 삭제해서 다시 재귀
  
}

//위 풀이 아래의 코드로 정리가능
function take(num, arr) {
  if(arr.length === 0) return []
  if(num >= arr.length) return arr
  return take(num, arr.slice(0,arr.length-1))
}

재귀함수 자체는 그 함수를 또다시 시작시키는 것이다.

그러므로 기억할 수 있는 값은, 다음 실행에 전달할 수 있는 값은 인자밖에 없으므로,

따라서 최종적으로 arr.length가 되어야할 num은 그대로 넘겨주어야하고, 

배열은 요소하나를 끝에서부터 잘라서 넘겨주어야 한다고 생각했다.

 

앞에서 부터 떼오는 것 같지만, 사실은 뒤에서부터 하나씩 자르는 것이다.

 

그런데 이런 문제를 풀어도 되긴 하지만,실질적으론 아주 비효율적이라고 생각이 들었다.

아래의 코드를 참고.

take(2,[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17])

//첫번째 풀이에 의하면 다음의 과정을 거친다.
take(2,[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16])
take(2,[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])
...13번 실행중...
take(2,[1,2])

그래서 뒤에서 제거가 아니라, 앞에서 부터 떼오는 방법엔 무엇이 있을까를 생각해보기로 했다.

 

 

두번째 풀이: 클로저 + 재귀함수 사용법

function take(num, arr) {
  //외부에서 arr 와 result에 모두 접근이 가능하다.
  let result = []

  //예외조건
  if (arr.length===0) return result
  if (num > arr.length) num = arr.length

  //재귀함수
  const aux = (num, arr)=>{
    //base case: num이 0이면 종료
    if(num === 0) return result
    //recursive case: 외부 result에 arr[0]을 하나씩 더해주기
    result.push(arr[0])
    //recursive case: num을 줄이고 arr에 하나를 빼서 다시 aux실행
    return aux(num-1,arr.slice(1))
  }
  
  return aux(num, arr) //재귀함수를 실행하고 결과 값인 arr를 리턴
}

이 방법은 클로저를 이용해서 외부변수에 접근이 가능하다는 점을 사용해서

외부에 result 배열에 요소를 하나씩 떼어놓는 방식으로 작동한다.

이로서 앞에서부터 떼온것을 저장 할 수 있게되었다.

 

 

세번째 풀이: 똑똑한 재귀함수 사용법

function take(num, arr) {
  // take(3,[1,2]) 
  // return [1].concat(take(2,[2]))
  // return [2].concat(take(1,[]))
  // return []
  
  // 아래 코드를 쓰지 않아도 위처럼 exception case 대응이 되지만, 
  // 쓸경우 재귀 자체를 안불러도 되어서 더 빠를 수 있다.
  
  // if (num >= arr.length) {
  //   return arr;
  // }

  if (num === 0 || arr.length === 0) {
    return []; //return arr를 해버리면 take(0,[1,2])와 같이 들어왔을 때 대응 못한다.
  }

  // const [head, ...tail] = arr;
  const head = arr[0];
  const tail = arr.slice(1);

  return [head].concat(take(num - 1, tail));
}

이 풀이는 레퍼런스 코드를 가져온 것으로, 클로저를 쓰지 않고 앞에서부터 떼올 수 있도록 했다.

코드가 짧고 간결해서 좋아보인다. 

 

---

재귀함수 문제02

 

문제:

선물 상자에 대한 정보를 담은 배열과 문자열을 입력받아 조건에 맞는 선물이 있는지 여부를 리턴해야 합니다.

 

입력:

인자1 : giftBox	인자2 : wish
문자열, 배열을 요소로 갖는 재귀적으로 정의된 배열 (입출력 예시 참고) 문자열은 선물 상자에 들어있는 각 선물의 이름을 의미합니다. 배열은 더 작은 선물 상자를 의미합니다.	string 타입의 문자열

 

출력:

• boolean 타입을 리턴해야 합니다.

 

주의사항:

• 함수 unpackGiftbox는 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용이 가능합니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• 빈 배열 또는 빈 문자열을 입력받은 경우, false를 리턴해야 합니다.

 

입출력 예시:

const giftBox = ['macbook', 'mugcup', ['eyephone', 'postcard'], 'money'];

let output = unpackGiftbox(giftBox, 'iphone');
console.log(output); // --> false

output = unpackGiftbox(giftBox, 'postcard');
console.log(output); // --> true

 

📝 이 문제는... 

if문과 함께 재귀함수를 걸어줘야 풀 수 있는데, 이게 의사코드랑 같이 꼼꼼히 정리하지 않으면 헷갈리기 쉽다.

 

 

첫번째 풀이: includes 사용

function unpackGiftbox(giftBox, wish) {
  //base case: 배열안에 배열을 타고 들어가지 않아도 요소로 바로 있는 경우
  if (giftBox.includes(wish)) {
    return true
  } else {
    //resursive case: 배열 안에 바로 있지 않은 경우
    for (let i = 0; i< giftBox.length; i++) { //요소를 하나 씩 돌면서
      if(Array.isArray(giftBox[i])){ //배열이 있다면 
        if(unpackGiftbox(giftBox[i],wish)){ //그거 또 열어보고 그 결과가 true라면
          return true //바깥에서도 return을 해서 for문을 중단시켜줘야함.
        }
        //그냥 return unpackGiftbox(giftBox[i],wish)일케 해버리면 요소중에 배열이 두개이상일 경우
        //giftBox[1]에 없어서 다음 giftBox[2]로 넘어가야할때 함수 자체가 return false로 끝나버림
      }
    }
    //base case: for문을 다 돌아도 true로 리턴된 것이 없으면 return false로 마무리
    return false
  }
}

위의 풀이 방법엔 아래와 같은 includes의 특징을 알아야한다.

const arr = ['a','b',['d','e']]

arr.includes('a') // ture
arr.includes('d') // false

---

재귀함수 문제03

 

문제:

배열을 입력받아 순서가 뒤집힌 배열을 리턴해야 합니다.

 

입력:

인자1 : arr

임의의 요소를 갖는 배열

 

출력:

• 순서가 뒤집힌 배열을 리턴해야 합니다.
• [arr[n-1], arr[n-2], ... , arr[0]]
• arr.length는 n

 

주의사항:

• 함수 reverseArr는 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• 빈 배열은 빈 배열 그대로를 리턴해야 합니다.

 

입출력 예시:

let output = reverseArr([1, 2, 3]);
console.log(output); // --> [3, 2, 1]

 

📝 이 문제는... 

개인적으로 재귀에서 제일 헷갈리는 부분은 어떤 부분을 재귀로 처리해줘야하는가 이다.

return문에서 그냥 일반 값의 처리와 재귀함수 재호출 부분이 같이 들어있을때 침착하게 적어야한다.

 

 

첫번째 풀이: 구조분해할당 이용

function reverseArr(arr) {
  //base case
  if(arr.length === 0) return []
  
  //recursive case: 
  //arr의 맨 뒷요소를 맨 앞에, 나머지 요소들을 가진 배열을다시 또 재귀로 돌린다.
  return [arr[arr.length-1],...reverseArr(arr.slice(0,arr.length-1))] 
  //[3, ...[1,2]] // [2, ...[1]] //[1,...[]] //[]
}

구조 분해 할당을 이용하니까 복잡하게 느껴진다. 

좋은 코드는 짧기만 하다고 다는 아니고, 가독성이 좋기도 해야하므로, 다른 풀이 방법이 좋겠다 생각했다.

 

 

두번째 풀이: concat 이용

function reverseArr(arr) {
  //base case
  if (arr.length === 0) {
    return [];
  }

  //recursive case: 변수와 concat을 이용해서 좀더 명확하게 기능이 보인다.
  // const [head, ...tail] = arr;
  const head = arr[0];
  const tail = arr.slice(1);
  return reverseArr(tail).concat(head);
}

레퍼런스 코드를 참고하였는데, 일단 head와 tail이라는 변수를 지정하면

return 문에서 head가 맨뒤에 붙고, tail이 앞에서 또 재귀함수로 돌아가는구나! 하는게 한눈에 보인다.

잘 지은 변수 이름(head,tail)이 이해하기가 쉽게 해준다.

 

---

추가: 피보나치 문제풀이 두가지: O(n),O(n^2)