[Javascript] 재귀 함수

재귀의 개념

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

이 개념을 함수에 넣으면 자기 자신을 끝없이 호출해 같은 코드를 반복해서 실행할 것이다. 이렇게 자기 자신을 호출하는 함수를 재귀 함수라고 한다. 재귀 함수를 활용하면 반복적인 작업을 해야 하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다.

재귀로 문제 해결하기

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

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;

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

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

재귀를 사용하는 경우

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

모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.