[자료구조/알고리즘] 재귀 + 연습문제,,

재귀란 무엇일까요? 표준국어대사전에서는 다음과 같이 정의하고 있습니다.

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.

재귀 ⇒

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우

배열 [1, 2, 3, 4, 5 ]의 합을 구하는 과정을 재귀

function arrSum (arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if (arr.length === 0) {
    return 0
  }

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr.shift() + arrSum(arr)
}

Guide : 재귀적으로 사고하기

1. 재귀 함수의 입력값과 출력값 정의하기

재귀적으로 사고하는 데에 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것입니다.

함수의 입출력값을 정의하는 것은 그 첫 출발점이며, 재귀 함수를 통해 풀고자 하는 문제,

즉 도달하고자 하는 목표를 정의하는 데 도움이 됩니다.

 

함수 arrSum 의 경우 number 타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴합니다.

이를 좀 더 간단하게 표기하면 다음과 같습니다.

• arrSum: [number] => number ← 입출력값 정의

 

 

2. 문제를 쪼개고 경우의 수를 나누기

문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인합니다.

일반적으로, 입력값을 이 기준으로 정합니다.

이때 중요한 관점은 입력값이나 문제의 순서와 크기입니다.

주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 됩니다.

그리고 구분된 문제를 푸는 방식이 순서나 크기와 관계없이 모두 같다면, 문제를 제대로 구분한 것입니다.

• 함수 arrSum 의 경우 입력값인 배열의 크기에 따라, 더 작은 문제로 나눌 수 있습니다. 그리고 arrSum([1, 2, 3, 4]) 를 구하는 방법과 arrSum([2, 3, 4]) 을 구하는 방법은 동일하므로, 이 구분은 적절하다고 판단할 수 있습니다.

이제 문제에서 주어진 입력값에 따라, 경우의 수를 나눕니다.

일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눕니다.

• 함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있습니다. 각각의 경우는 다른 방식으로 처리해야 합니다.
  • arrSum: [number] => number
  • arrSum([ ]) ← 입력값이 빈 배열인 경우
  • arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우

 

 

3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결합니다.

이를 재귀의 기초(base case)라고 부릅니다.

재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성합니다.

탈출 조건이 없는 경우 재귀 함수는 끝없이 자기 자신을 호출하게 됩니다.

그렇다고 문제를 덜 쪼갠 상태에서 탈출 조건을 세우는 경우 문제를 제대로 해결할 수 없게 됩니다. 그만큼 문제를 최대한 작게 쪼갠 후에 문제를 해결하는 것이 중요합니다.

• 함수 arrSum 을 더이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은 0입니다.
  • arrSum: [number] => number
  • arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결!
  • arrSum([요소1, 요소2, ... , 요소n])

 

 

4. 복잡한 문제 해결하기

남아있는 복잡한 경우를 해결합니다.

• 길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더합니다.
• arrSum: [number] => number
• arrSum([ ]) === 0
• arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) ← 그렇지 않은 경우 : 해결!
• 배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수 arrSum 을 재귀적으로 구현할 수 있습니다.

 

 

 

5. 코드 구현하기

function arrSum(arr) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }

  // recursive case : 그렇지 않은 경우
  return 요소1 + arrSum([요소2, ... , 요소n]);
}

아래는 일반적인 재귀 함수의 템플릿입니다.

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

 

팩토리얼 (Factorial) 구하기

function factorial (n) {

  if (n === 1) { 	// Base case, Termination case

    return 1;
  }

  return n * factorial(n - 1);
}

factorial(3);	 // 6

• 재귀 함수의 대표적인 예제 코드가 바로 팩토리얼 구하기이다.

 

---

 

연습문제 12번 reverseArr

 

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

function reverseArr(arr) {
  // 빈 배열은 빈 배열 그대로를 리턴해야 합니다.
  if(arr.length === 0) return arr

    // 배열의 0번째 인덱스를 분리
    let head = arr[0]
    // 0번째 인덱스를 제외한 나머지 배열을 tail 할당
    let tail = arr.slice(1)

    // 그리고 분리된 0번째 인덱스를 나머지 배열 뒤에
    // concat하면 배열 뒤쪽으로 추가할 수 있다.
    return reverseArr(tail).concat(head)

}

 

 

연습문제 13번 findMatryoshka

 

→ 마트료시카 있는지 확인

function findMatryoshka(matryoshka, size) {
  // 빈 객체를 입력받은 경우, false를 리턴해야 합니다.
  if (Object.keys(matryoshka).length === 0) {
    return false
  }
  // 내가 찾는 마트료시카가 있다? -> true
  if(matryoshka.size === size) {
    return true
  }
  // 마트료시카가 안에 또 있을때, 재귀호출
  if(matryoshka.matryoshka !== null) {
    return findMatryoshka(matryoshka.matryoshka, size)
  }

  // 이제 찾는 마트료 시카가 없다~
  return false
}

 

연습문제 14 unpackGiftbox

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

function unpackGiftbox(giftBox, wish) {

  // if(giftBox.length === 0) false
  // if(wish.length === 0) false

  for (let i = 0; i < giftBox.length; i++) {
    if (giftBox[i] === wish) { 
      return true;
    } else if (Array.isArray(giftBox[i])) {
      // 재귀 돌며 배열 안의 배열 스트링과 wish와 같은지 비교하여
      const result = unpackGiftbox(giftBox[i], wish);
      // 같으면 true
      if (result === true) {
        return true;
      }
    }
  }
  return false
}