#7 재귀함수에 관해서 🧐

오늘은 재귀함수라는 아주 무지막지한 함수를 배웠다. 재귀함수는 반복문(for,while)처럼 사용이 가능하며 자바스크립트에서 꼭 필요한 함수라고 알려주셨다.

재귀란? 어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 이야기한다.

이러한 재귀함수를 어디에 사용하면 좋을까?

재귀는 특히 아래와 같은 상황에서 매우 적합하다.주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우

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);
                           }
                        }
                    }
                }
            }
        }
    }
 }

사실 모든 재귀 함수는 재귀 호출 없이 while / for loop으로 표현이 가능하다. 하지만 재귀를 사용 가능한 경우, 재귀를 사용한 코드가 대부분의 경우 더욱 간결하고, 일부의 경우에는 이해하기도 쉽습니다. 이 장이 끝나고 검색 과제로 주어지는 하노이의 탑을 찾아보는 것도 좋을 것 같다.

재귀는 쪼개는 방법??

1. 원래의 문제에서 출발하여 더 작은 경우를 생각합니다.

arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);

2.계속해서 문제가 더는 작아지지 않을 때까지 더 작은 경우를 생각합니다.

arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);

3.이렇게 문제 풀기를 미루다가, 문제가 간단해져서 바로 풀 수 있게 되는 순간에 미뤄왔던 문제들을 차근차근 해결합니다.

arrSum([]) = 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용한다.
arrSum([2]) = 2 + arrSum([]) = 2;
arrSum([6, 2]) = 6 + arrSum([2]) = 6 + 2 = 8;
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]) = 3 + 8 = 11;
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]) = 10 + 11 = 21;

4. arrSum을 아래와 엄밀하게 바꾸면

arrSum(arr)
1. arr이 빈 배열인 경우 = 0
2. 그 외의 경우 = arr[0] + arrSum(arr2)
   (arr2는 arr의 첫 요소를 제외한 나머지 배열)

이제 재귀함수를 코드를 구현을 하게되면

function arrSum(arr) {
// 재귀의 기초 (base case)
// 문제를 더 이상 쪼갤 수 없을 경우
if (arr의 길이가 0인 경우) {
    return 0;
}
// recursive Case
// 그렇지 않은 경우
// head: 배열의 첫 요소
// tail: 배열의 첫 요소만 제거된 배열
return head + arrSum(tail);
}

아래는 일반적인 재귀 함수의 템플릿입니다. 재귀 함수 연습에 활용하시기 바랍니다.

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

재귀함수는 매우 중요한 함수이고 기업들의 코딩테스트에는 무조건 나오는 함수이기에 열심히 이해를 하면서 공부를 해야할꺼같다.😭 Full pre 11기 화이팅👍