JavaScript_재귀

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.
재귀함수는, 자기 자신을 호출하는 함수를 말한다.

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

arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5])
...
arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])

이로써 문제를 가장 작은 단위까지 조갰다고 할 수 있다.

문제 해결하기

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([]) 이다. 빈 배열의 합은 0이므로, 0을 리턴해주면 된다. 이렇게 가장 작은 문제를 해결하는 순간, 아래 코드처럼 쪼개졌던 문제가 거꾸로 거슬러 올라가면서 합쳐지게 된다.

arrSum([]) 는 조건문에 의해 더이상 자기자신을 호출하지 않고, 숫자 0을 리턴하면서 종료된다. 그 결과 중첩되어있던 함수들도 연쇄적으로 숫자를 리턴하고, 최종적으로는 배열의 모든 요소의 합을 리턴하면서 문제가 해결된다.

재귀는 언제 사용하는 게 좋을까?

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
   
   모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있습니다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.

fibonnaci 예시

function fibonacci(n) {
  if(n<=1)return n;
  return fibonacci(n-1) + fibonacci(n-2)
  //0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
}