재귀 함수

• 자기 자신을 호출하는 함수
• 재귀(recursion) : 원래의 자리로 되돌아가거나 되돌아옴
• 자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행
• 반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있음

재귀로 문제 해결하기

• 문제를 좀 더 작게 쪼갭니다.
• 위와 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갭니다.
• 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결합니다.

Q. 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 arrSum 을 작성하세요.

// 1. 문제를 작게 쪼개기
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5])
...

// 2. 문제를 가장 작은 단위로 쪼개기
...
arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])

// 3. 문제 해결하기
arrSum([]) === 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용합니다.
arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5;
arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9;
arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12;
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14;
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15;

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

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

재귀를 사용하기 적합한 상황

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
• 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

재귀의 활용

1. 재귀 함수의 입력값과 출력값 정의하기 : 가장 단순하게 정의
2. 문제를 쪼개고 경우의 수를 나누기 → 이때 중요한 관점은 입력값이나 문제의 순서와 크기
3. 단순한 문제 해결하기 : 재귀의 기초 → 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성
4. 남아있는 복잡한 문제 해결하고, 코드 구현하기

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

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

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

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

Q. 자연수를 입력받고, 입력받은 수부터 1까지의 자연수를 모두 곱한 값을 리턴하는 재귀 함수 fac 을 작성하세요.

function fac(n) {
  if (n === 1) {
    return 1;
  }
  return n * fac(n-1);
}

// fac(5)  ===  5 * 4 * 3 * 2 * 1  ===  120
// fac(3)  ===  3 * 2 * 1  ===  6