01. 재귀함수

---

재귀 함수란 “자기 자신을 호출하는 함수”를 말한다.

🔨 1. 재귀로 문제 해결하기

문제 : 자연수로 이루어진 리스트(배열)을 입력받고, 리스트의 합을 리턴하는 함수 'arrSum'을 작성하세요.
 *배열 : [1, 2, 3, 4, 5]

1. 문제를 작게 쪼갠다.
2. 문제가 더 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갠다.
3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.

🔧 1-1. 문제 작게 쪼개기

arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) //arrSum([1, 2, 3, 4, 5])보다 arrSum([2, 3, 4, 5])더 작은 단위,
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) //arrSum([2, 3, 4, 5])보다 arrSum([3, 4, 5])가 더 작은 단위이다.
...

🔧 1-2. 문제를 가장 작은 단위로 쪼개기

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

🔧 1-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으로 표현한다면 다음과 같다.

//arr = [1, 2, 3, 4, 5]

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

//배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수 --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
return arr.shift() + arrSum(arr)
}
==================================================
//!해석
1. 만약 배열이 빈 배열(arr.length === 0)이면 0을 리턴하고,
2. 빈 배열이 아니라면, 3번을 리턴하라.
3. arr의 제거된 첫번째 요소와 + arrSum(arr)을 리턴하라.
 그럼 순차적으로
 1번 return arr.shift() + arrSum(arr) // 1 + [2, 3, 4, 5]
 2번 return arr.shift() + arrSum(arr) // 3 + [3, 4, 5]
 3번 return arr.shift() + arrSum(arr) // 6 + [4, 5]
 4번 return arr.shift() + arrSum(arr) // 10 + [5]
 5번 return arr.shift() + arrSum(arr) // 15 + [] ->  (arr.length === 0)이므로 함수를 빠져나간다

💡 arr.shift() : 배열의 맨 처음 요소를 제거한다.

• 0번째 위치의 요소를 제거 하고 연이은 나머지 값들의 위치를 한칸 씩 앞으로 당긴 후 → 제거된 값을 반환한다.
• 빈 배열일 경우엔 [undefined](https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/undefined)를 반환한다.

let myFish = ['angel', 'clown', 'mandarin', 'surgeon'];
let shifted = myFish.shift();

return myFish // --> ['clown', 'mandarin', 'surgeon']r
return shifted // --> 'angel'

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

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩횟수를 예측하기 어려운 경우

3. 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

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

• 게다가 재귀는 알고리즘 문제의 많은 부분을 차지한다 → 입사 코딩 테스트에 많이 쓰임.