CH1. 재귀 (Recursion)

📌 재귀의 이해

재귀의 개념

🔸 재귀는 원래의 자리로 되돌아가거나 되돌아온다는 뜻.
🔸 자기 자신을 호출하는 함수를 재귀 함수라고 함.

function recursion() {
	console.log('hello');
    recursion();
} // `recursion` 함수를 호출하면 무한 루프 발생

재귀로 문제 해결하기

🔸 반복적인 작업을 해야하는 문제를 좀 더 간결하게 작성할 수 있음

1. 문제를 동일한 방식으로 작게 쪼개기 : recursive case

2. 문제를 더이상 안 쪼개지는 가장 작은 단위로 쪼개기 : base case

3. 문제 해결하기 : base case 해결하기

1. 문제를 작게 쪼개기

/* 배열의 합을 구할 때 [1, 2, 3]의 합을 구하는 것보다
[2, 3]의 합을 구하는 것이 더 작은 문제 ... */

arrSum([1, 2, 3]) === 1 + arrSum([2, 3])
arrSum([2,3]) === 2 + arrSum([3])

2. 문제를 가장 작은 단위로 쪼개기

// 위에서 문제를 쪼갠 방식을 반복해서 문제를 쪼개면 더이상 쪼갤 수 없는 상태 도달
arrSum([1,2,3]) === 1 + arrSum([2,3])
arrSum([2,3]) === 2 + arrSum([3])
arrSum([3]) === 3 + arrSum([])

3. 문제 해결하기

/* 문제를 쪼갤 때 같은 방식으로 쪼갰기 때문에
가장 작은 단위의 문제를 해결한 방식으로 문제 전체를 해결 가능 */
arrSum([]) === 0  // 문제가 더는 작아지지 않는 순간
arrSum([3]) === 3 + arrSum([]) === 3 + 0 === 3
arrSum([2,3]) ===  2 + arrSum([3]) === 2 + 3 === 5
arrSum([1,2,3]) === 1 + arrSum([2,3]) === 1 + 5 === 6

🔸 위의 단계를 반영해 자연수로 이루어진 배열을 입력받고, 배열의 합을 리턴하는 함수 arrSum 작성.

function arrSum (arr) {
  // 빈 배열을 입력 받았을 때 0을 리턴하는 조건문
  // 가장 작은 문제를 해결하는 코드, 재귀를 멈추는 코드
  if(arr.length === 0) {
    return 0
  }
  
  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  // 재귀(자기 자신 호출)를 통해 문제를 작게 쪼개나가는 코드
  return arr.shift() + arrSum(arr)

아래와 같은 상황에서 재귀를 사용하기 적합

🔸 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
🔸 중첩된 반복문이 많거나 반복문의 중첩횟수를 예측하기 어려운 경우

📌 재귀적으로 사고하기

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

🔸 문제를 가장 단순하게 정의

• 함수 arrSum의 경우 number 타입의 요소로 갖는 배열을 입력받고, number 타입을 리턴
• srrSum: [number] => number 입출력값 정의

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

🔸 문제를 어떻게 쪼갤 것인지 기준을 정함.

🔸 입력값이나 문제의 순서와 크기로 경우의 수를 나눔.

• 함수 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]) 그렇지 않은 경우 : "해결"
  • 배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수 arrSum을 재귀적으로 구현 가능.

5. 코드 구현하기

function arrSum(arr) {
  // 📍 base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0; // 단순한 문제의 해답;
  }
  
  // 📍 recursive case : 그렇지 않은 경우
  return 요소1 + arrSum([요소2, ... , 요소n]); // 더 작은 문제로 새롭게 정의된 문제
}