자바스크립트로 설명하는 재귀함수

1. 재귀함수

• 재귀: 자기 자신을 호출하는 절차.
• 재귀 호출: 함수가 자기 자신을 호출하는 것.(recursive call)
• 재귀 함수: 재귀 호출을 수행하는 함수. 즉 자기 자신을 호출하는 함수를 말한다.
• 재귀 함수는 반복되는 처리 를 위해 사용한다. 주로 아래 경우에서 많이 사용한다.
  • JSON.parse() 를 호출하는 JSON.parse()
  • 팩토리얼
  • DOM 순회
  • 객체 순회
  • 자료구조 구현
• 모든 경우에서 반복문을 대체함이 아닌, 재귀함수를 사용하는 것이 더 코드를 이해하기 쉬운 경우에 사용한다.
• 탈출 조건이 없으면 무한반복 하여 스택 오버플로우 되므로 반드시 탈출 조건이 주어져야 한다! (탈출 조건: base case)
• 반복되면서 입력받을 값 또한 계속 바뀌어야 한다. 그렇지 않으면 계속 같은 값만 확인하고 같은 결과만 받게 된다.
• 콜 스택:
  • 자바스크립트에서 함수의 실행 순서를 결정하는 자료구조이다.
  • 스크립트가 함수 호출 → 인터프리터가 콜스택에 추가 → 함수 실행
  • 선입선출(FIFO) 방식이다.

1.1 재귀함수의 여러 형태

1.1.1 가장 기본적인 형태

function recursive(num) {
  if (num <= 0) {
    return console.log('탈출 조건에 걸려 재귀함수 종료.');
  }
  console.log(num);
  num--;
  recursive(num);
}
recursive(5);

// 5
// 4
// 3
// 2
// 1
// 탈출 조건에 걸려 재귀함수 종료.

• 재귀 함수의 필수 구성요소: 1. 탈출 조건 (조건문, 비교할 값의 변화)
• 재귀 함수는 탈출 조건(base case)이 없는 경우 무한반복되어 스택 오버플로우 현상이 발생된다.
• 따라서 탈출 조건이 주어져야 하며, 반복 시마다 값 또한 변화되어야 계속 같은 값으로 같은 결과를 내는 것을 막을 수 있다.

1.1.2 반환값이 2번 등장한 형태

function sumOfAll(num) {
  if (num === 1) return 1;
  return num + sumOfAll(num - 1);
}
sumOfAll(3); // 6

/**
 * sumOfAll(3)
 *      return 3 + sumOfAll(2)
 *                  return 2 + sumOfAll(1)
 *                                  return 1
 */

• 탈출 조건에서 반환값을 받아 마지막 재귀 호출의 반환값으로 하여 뎁스를 올라가며 최종적으로 재귀 함수 호출의 반환값을 반환하고 함수가 종료된다.
• 즉 콜 스택에 쌓인 재귀 함수 호출이 탈출 조건을 만나면서 하나씩 실행되며 return value가 변화하면서 최종적으로 원하는 결과를 반환한다.

1.1.3 재귀 함수로 팩토리얼 구현하기

• 팩토리얼: 주어진 수 부터 1까지 차례로 곱하기 ex: !4 = 4 * 3 * 2 * 1

// * 1. 반복문으로 팩토리얼 구현하기
function factorial(num) {
  let result = 1; // 초기값을 1로 주어야 *= 해서 값이 들어간다.
  for (let i = num; i > 0; i--) {
    result *= i;
  }
  return result;
}
factorial(4); // 24

// * 2. 재귀 함수로 팩토리얼 구현하기
function factorial(num) {
  if (num == 1) return 1; // 이 탈출 조건이 주어지지 않으면 무한반복.
  return num * factorial(num - 1);
}
factorial(4); // 24

1.1.4 헬퍼 메서드 재귀( = 헬퍼 함수인 재귀 함수)

function collectEvenNums(arr) {
  let result = [];

  function helper(changingInput) {
    if (changingInput.length === 0) return;

    if (changingInput[0] % 2 === 0) {
      result.push(changingInput[0]);
    }

    helper(changingInput.slice(1));
  }

  helper(arr);

  return result;
}

const arrInGlobal = [1, 2, 3, 4, 5, 6];

collectEvenNums(arrInGlobal); // [2, 4, 6]

• 헬퍼 함수(보조 함수): 어떤 함수에서 호출되는 다른 함수. 외부 함수의 반환값으로 호출되거나, 외부 함수의 반환값 이전에 호출되어 외부 함수의 반환값을 의도대로 변경시킨다.

1.1.5 순수 재귀

• 헬퍼 함수 없이 재귀 함수 안에서 재귀 호출만으로 구현되었다.

// * 순수 재귀

function collectEvenNums(arr) {
  // * newArr은 반복 할 때마다 빈 배열로 초기화된다.
  // * 하지만 arr이 재귀 호출시마다 slice된다.
  let newArr = [];

  if (arr.length === 0) return newArr;

  if (arr[0] % 2 === 0) {
    newArr.push(arr[0]);
  }
  // * 새 배열을 재할당하면서 concat 메서드 안에서 재귀 호출이 일어난다.
  newArr = newArr.concat(collectEvenNums(arr.slice(1)));
  return newArr;
}

const arrInGlobal = [1, 2, 3, 4, 5, 6];

collectEvenNums(arrInGlobal); // [2, 4, 6]

/**
 * [].concat(collectEvenNums([2,3,4,5,6]))
 *            [2].concat(collectEvenNums([3,4,5,6]))
 *                         [].concat(collectEvenNums([4,5,6]))
 *                                    [4].concat(collectEvenNums([5,6]))
 *                                                [].concat(collectEvenNum([6]))
 *                                                              [6]
 */

참고자료

• 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스 링크
• 모던 자바스크립트 딥 다이브 12장 - 함수
• 콜스택이란 링크