21년 1월 1일 TIL

JavaScript Recursion (재귀 함수)

- 재귀함수(Recursion Function)란 함수 내에서 함수 자신을 호출하는 함수이다.

- 구조가 비슷한, 주어진 문제가 더 작은 문제로 나누어 질 수 있는 경우 사용

- 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우 사용

 

함수내에서, 자기 자신을 계속 호출하여 더이상 더 작아질 수 없는 선까지 도달한 이후에 다시 돌아가서 값을 가져온다.

 

학창시절에 배웠던 팩토리얼을 떠올려보자. 4!의 경우 4 * 3 * 2 * 1이고 답은 24이다. 이것을 for문으로 표현하면

let arr = [1, 2, 3, 4]
let result = 1;

function factorial(arr) {
  for (let i = 0; i < arr.length; i++) {
    result = result * arr[i];
  }
  return result;
}

이렇게 될 것이다.

재귀함수로 표현을 한다면 아래와 같다.

let arr = [1, 2, 3 ,4]

function factorial(arr) {
  if (arr.length === 0) {
    return 1;
  }
  let head = arr[0];
  let tail = arr.slice(1);
  
  return head * factorial(tail);
}

// 1번째 호출시 1 * factorial([2, 3, 4])
// 2번째 호출시 2 * factorial([3, 4])
// 3번째 호출시 3 * factorial([4])
// 4번째 호출시 4 * factorial([])
// arr.length === 0 일때 return 1 임으로 factoril([])는 1
// 더이상 쪼개질 수 없음으로 다시 4번째부터 1번째까지 돌아간다.
// 4번째 호출 4 * 1 = 4
// 3번째 호출 3 * 4 = 12
// 2번째 호출 2 * 12 = 24
// 1번째 호출 1 * 24 = 24 ---> 24 리턴.

위와 같은 예시는 간단하므로 for문으로 해결이 가능하다. 이러한 경우에는 굳이 사용하지 않아도 충분히 해결할 수 있으나

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

이와같이 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우는 재귀함수를 사용하는것이 효율적이고 간단하다.

 

스스로를 호출한다는 부분이 처음에 이해하기 어려웠지만. 하나하나씩 적어가며 하다보니 이해가 되었다. 자바스크립트의 알고리즘에 단골 문제로 나오는 재귀함수라고하니 필수적으로 개념을 이해하고 넘어가는 것이 필요하다.