[Section 3] 재귀

재귀란?

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.
재귀의 시각적 예시를 든다면 계속해서 원래의 상태로 돌아오는 아래 이미지와 같을 것이다.

재귀로 문제 해결하기

1. 문제를 작게 쪼개기

arrSum 함수로 [1, 2, 3, 4, 5] 의 합을 구하는 과정

배열의 합을 구할 때 [1, 2, 3, 4, 5] 의 합을 구하는 것보다
[2, 3, 4, 5] 의 합을 구하는 것이 더 작은 문제이고,
또 [2, 3, 4, 5]의 합을 구하는 것보다
[3, 4, 5] 의 합을 구하는 것이 더 작은 문제일 것이다.

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([])

마지막에는 arrSum 이 빈 배열을 받게 되면서 문제를 더 이상 쪼갤 수 없게 되어 가장 작은 단위까지 쪼갠다.

3. 문제 해결하기

문제가 더 쪼개지지 않게 되면 가장 작은 단위의 문제를 해결한다.
2번에서 가장 작은 문제는 arrSum([]) 이다. 빈 배열의 합은 0이므로, 0을 리턴해주면 된다.

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;

문제 해결

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

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

---