재귀(Recursion)

1. 재귀란?

컴퓨터 과학에서 재귀(recursion)은 자신을 정의할 때 자기 자신을 참조하는 것이라고 합니다. 프로그래밍에서 재귀함수는 자기 자신을 호출하도록 정의한 함수입니다.

1. 1. 재귀함수의 구성요소

재귀함수는 베이스(base case)와 재귀단계(recursive case)로 구성됩니다. x를 n 제곱하는 함수 pow(x, n)을 예시로 재귀함수의 구성과 작동원리를 이해해봅시다.

function pow(x, n) {
  if (n === 1) {
    return x; // Base case
  };

  return x * pow(x, n - 1); // Recursive case

이 함수는 다음 단계로 나누어져 실행됩니다.

graph LR A["pow(x, n)"] --> B{"n === 1?"} B -- "No" --> C("x * pow(x, n-1)") C -- "recursive call until n === 1" --> A B -- "Yes" --> D("return x")

Base case( n=== 1 ): 즉시 x에 해당하는 값을 반환합니다.

Recursive case( n !== 1): pow(x, n) 은 x * pow(x, n-1)으로 표현할 수 있습니다. 즉, pow(x, n)은 pow(x, n-1)을 참조해야 하며, Base case에 도달할 때까지 서브함수를 참조하는 재귀단계를 반복합니다.

따라서, pow(2, 4)를 실행하면 다음과 같은 4단계로 재귀함수를 호출합니다.

stage 1: pow(2, 4) = 2 * pow(2, 3)
stage 2: pow(2, 3) = 2 * pow(2, 2)
stage 3: pow(2, 2) = 2 * pow(2, 1)
stage 4: pow(2, 1) = 2

1. 2. 서브호출(subcall)과 실행 컨텍스트(Execution Context)

pow(2, 4)를 실행하면 순차적으로 pow(2, 3)에서 pow(2, 1)까지 생성됩니다. 실행 중인 함수의 정보는 함수의 실행 컨텍스트(Execution Context)에 저장됩니다. 함수 호출 1회마다 하나의 실행 컨텍스트가 실행됩니다. 예제에서는 총 4개의 컨텍스트가 생성됩니다.

graph TB subgraph step 4 G["context: {x: 2, n: 1}"] --- H["context {x: 2, n: 2}"] H --- I["context: {x: 2, n: 3}"] I --- J["context: {x: 2, n: 4}"] end subgraph step 3 D["context: {x: 2, n: 2}"] --- E["context: {x: 2, n: 3}"] E --- F["context: {x: 2, n: 4}"] end subgraph step 2 B["context: {x: 2, n: 3}"] --- C["context: {x: 2, n: 4}"] end subgraph step 1 A["context: {x: 2, n: 4}"] end

첫 호출 pow(2, 4)를 계산하려면 새로운 서브 호출(subcall) pow(2, 3)을 만들어야 합니다. 새로 만들어진 실행 컨텍스트는 스택 최상단에 위치하게 됩니다. 이전 실행 컨텍스트인 pow(2, 4)는 중지된 상태로 남게됩니다. 동일한 과정을 pow(2, 1)까지 반복합니다.

graph TB subgraph step 5-8 A["context: {x: 2, n: 1}"] --"return 2, destroy current context"--> B["context {x: 2, n: 2}"] B --"return 4, destroy current context"--> C["context: {x: 2, n: 3}"] C --"return 8, destroy current context"--> D["context: {x: 2, n: 4}"] D --"return 16", destroy current context--> E("result = 16") end

pow(2, 1)이 실행되면 상황이 달라집니다. base case(n === 1)을 만족하여 2가 반환됩니다. 서브호출 없이 함수가 종료되었죠. 함수가 종료되면 상응하는 실행컨텍스트는 메모리에서 폐기됩니다. 최상단 컨텍스트가 삭제되면, 바로 아래에 있는 컨텍스트가 최상단 컨텍스트가 되어 반환값을 받아 다시 실행됩니다. 이 과정을 실행 컨텍스트가 스택에 쌓일 때의 역순으로 반복하게 됩니다.

실행 컨텍스트는 그 함수가 종료되어 폐기되기 전까지 메모리를 차지하게 됩니다. 따라서, 재귀함수를 사용할 땐 메모리 요구사항을 유의해야 합니다. 보통 위와 같은 단편적인 문제는 반복문 기반의 알고리즘을 사용하는 것이 효과적입니다.

함수를 호출할 때 함수의 입력값 (매개 변수: argument), 리턴값, 리턴됐을 때 돌아갈 위치값 등을 스택에 저장한다. 재귀함수를 사용하면 함수가 끝나지 않은 채 연속적으로 함수를 호출하므로 스택에 메모리가 쌓이게 된다. 이 때문에 스택의 최대 크기 이상의 메모리가 쌓이게 되면 스택 오버 플로우가 일어나게 된다. 잦은 점프의 반복으로 성능이 저하될 위험도 있다.

1. 3. 꼬리 재귀(Tail recursion)

꼬리재귀는 재귀함수의 단점인 지나친 메모리 점유율을 해결하기 위한 호출방식 중 하나입니다. 재귀함수의 실행결과가 연산에 사용되지 않고 바로 반환되도록 하여 이전 함수의 상태를 유지할 필요가 없도록 함수를 작성하는 것입니다. 꼬리 재귀가 정상적으로 동작하려면 플랫폼에서 TGO(Tail Call Optimization)을 지원해야 합니다.

// 일반 재귀함수
function factorial(n) {
  if (n === 1) {
    return 1;
  };
  return n * factorial(n - 1);
};

// 꼬리 재귀함수
function factorial(n) {
  function factorialTail(n, acc) {
    if (n === 1) {
      return acc;
    };
    return factorialTail(n - 1, acc * n);
  };
  return factorialTail(n, 1);
};

꼬리재귀 함수는 acc(accumulator)라는 인자를 하나 더 가지고 있습니다. 보이지는 않지만, 컴파일러가 꼬리재귀 함수를 반복문으로 바꾸어줍니다. 실제 동작 또한 스택을 한 번만 호출하게 됩니다.

자세한 내용은 레퍼런스 중 꼬리재귀 함수 관련 내용을 참조할 것.

2. Reference

• https://ko.javascript.info/recursion
• https://bozeury.tistory.com/entry/꼬리-재귀-최적화Tail-Recursion