[Javascript] 재귀 함수가 뭔데, 그거 어떻게 하는 건데.

재귀 함수는...

재귀 함수는 자기 자신을 호출하는 함수이다. 자기 자신을 호출한다는게 무슨 뜻이냐면 아래 코드처럼 함수 안에 자기 자신을 또 부르는 것이다.

function repeat(){
  console.log("반복된다!");
  repeat();
}

repeat 함수를 콘솔에 출력해보면 "반복된다!"라는 문자열이 계속 출력되는 것을 볼 수 있다. 이는 함수 마지막에 repeat 함수를 다시 호출하기 때문이다.

🖐 재귀 함수를 왜 알아야 하나요?
재귀 함수를 사용하면 반복적인 작업을 좀 더 간단하게 풀어낼 수 있기 때문이다.

재귀를 사용해서 문제를 풀어보자

이론적으로 재귀로 문제를 해결하는 단계는 아래와 같다.

1. 문제를 좀 더 작게 쪼갠다.
2. 전과 같은 방식으로 문제가 더 작아질 수 없을 때까지 쪼갠다.
3. 가장 작은 단위의 문제를 풀어 전체 문제를 해결한다.

정리하자면 문제를 가장 작은 단위까지 쪼개서 해결한다! 이 개념을 적용해서 배열 [1,2,3,4,5]의 합을 구하는 함수를 작성해보자.

1. 문제를 좀 더 작게 쪼갠다.

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])
...

2. 전과 같은 방식으로 문제가 더 작아질 수 없을 때까지 쪼갠다.

arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([]) // 더 이상 쪼갤 수 없음

3. 가장 작은 단위의 문제를 풀어 전체 문제를 해결한다.

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 sum(arr){
    // 빈 배열을 받았을 때 0 리턴
    // 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
    if(arr.length === 0){
    	return 0;
    }
  
    // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 sum 함수
    // 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr.shift() + sum(arr);
}

재귀 함수 언제 사용하면 좋을까?

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