[JS] 꼬리재귀

 

*  레퍼런스
재귀와 스택 (JAVASCRIPT.INFO)

 

재귀 함수와 메모리 사용량 간의 관계

(javascript recursion memory leak) 

 

• 재귀함수는 함수 내에서 자기 자신을 호출하는 것을 말한다. ([JS]재귀 포스팅)
• 이를 통해 코드를 간결하고 이해하기 쉽게 만들 수 있다.
• 그러나 재귀함수는 메모리 사용량을 증가시키는 경향이 있다.

 

그 전에 알아야 하는 용어

• 실행 컨텍스트(execution context) :
  • 자바스크립트 엔진은 함수가 호출될 때마다 호출된 함수를 위한 실행 컨텍스트를 생성한다.
• 호출 스택(call stack) :
  • 코드가 실행되면서 생성되는 실행 컨텍스트를 저장하는 자료 구조이다.
  • 엔진이 함수를 호출할 때마다 함수를 위한 실행 컨텍스트를 생성하고 이를 콜 스택에 push한다.

 

---

 

재귀함수가 호출될 때마다, 함수의 호출 정보(함수의 매개변수, 지역 변수 및 반환 주소 등)를 저장하기 위한 메모리가 필요하다. 

• 재귀함수를 사용하면 함수가 끝나지 않은 채 연속적으로 함수를 호출하므로 실행 컨텍스트가 점점 쌓이게 된다.
• 스택은 쌓이고 쌓이다가, 함수 호출이 끝날 때(base case를 만날 때) 역순으로 처리된다. 
• 이렇게 역순으로 처리하면 스택의 맨 위에 있는 호출이 먼저 완료된다. 
• 이런 방식으로 메모리 사용량이 증가하는 것이며,
• 콜스택이 너무 깊어져 스택의 최대 크기 이상의 메모리가 쌓이게 되면 메모리 오버헤드(stack overflow)가 발생할 수 있다.

 

 

아래의 함수를 반복문과 재귀함수로 만들어 비교해보자.

 

x를 n 제곱해 주는 함수 pow(x, n)

예시:
pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

 

반복문 (for문 사용)

function pow(x, n) {
  let result = 1;

  // 반복문을 돌면서 x를 n번 곱함
  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

alert( pow(2, 3) ); // 8

 

• 반복문 기반 알고리즘은 메모리를 절약할 수 있다.
• 반복을 사용해 만든 함수 pow는 컨텍스트를 하나만 사용한다.
  • 이 컨텍스트에서는 i, result 가 변경된다.
  • 실행 컨텍스트가 하나이기 때문에 n에 의존적이지 않고, 필요한 메모리가 적다.
  • 사용 메모리 공간도 고정된다.

 

재귀호출 방법의 실행 컨텍스트의 수는 1개이다.

 

 

재귀 호출 (조건 연산자 사용)

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

alert( pow(2, 3) ); // 8

 

• 재귀를 사용한 코드는 반복적 사고에 근거하여 작성한 코드보다 대개 짧다.
• 코드를 단순화할 수 있다.
• 가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수는 재귀 깊이(recursion depth) 라고 한다. 
  • 재귀 함수의 호출 횟수는 스택의 남은 공간과 재귀 함수의 지역 변수 사이즈에 따라 달라진다.
  • pow(x, n)의 재귀 깊이는 n이다.
  • 재귀의 깊이는 스택에 들어가는 실행 컨텍스트 수의 최댓값과 같다.

 

재귀호출 방법의 실행 컨텍스트의 수는 n개이다.

 

그럼에도 재귀를 사용하는 이유

그럼에도 불구하고, 재귀를 사용하는 이유는 아래와 같다.

• 재귀를 사용하면 코드가 짧아지고 코드 이해도가 높아지며 유지보수에도 이점이 있다.
• 모든 곳에서 메모리 최적화를 신경 써서 코드를 작성해야 하는 것은 아니다.  

 

** 자바스크립트 엔진은 최대 재귀 깊이를 제한한다.

• 만개 정도까진 확실히 허용하고, 엔진에 따라 이보다 더 많은 깊이를 허용하는 경우도 있다.
• 하지만 대다수의 엔진이 십만까지는 다루지 못한다.
• 이런 제한을 완화하려고 엔진 내부에서 자동으로 '(꼬리 물기 최적화)tail-call optimization’라는 최적화를 수행하긴 하지만, 모든 곳에 적용되는 것은 아니고 간단한 경우에만 적용된다.

 

---

 

꼬리 물기 최적화 (TCO; Tail-Call Optimization)

 

자바스크립트 엔진은 최대 재귀 깊이를 제한한다.
재귀 깊이 제한 때문에 재귀를 실제 적용하는데 제약이 있긴 하지만, 재귀는 여전히 광범위하게 사용되고 있다.
재귀를 사용하면, 간결하고 유지보수가 쉬운 코드를 만들 수 있기 때문이다.
제한을 완화하려고 엔진 내부에서 자동으로 '꼬리 물기 최적화(TCO)’를 수행하는 경우가 있다.

 

꼬리 재귀 함수(tail-recursive function)

꼬리 재귀는 재귀호출을 할 때, 호출 후에 더 이상 실행할 코드가 없는 경우를 말한다. 

• 이 경우, 함수가 반환될 때마다 호출 스택에서 해당 호출을 제거한다.
• 이러한 형태의 함수를 "꼬리 재귀 함수(tail-recursive function)"라고 한다.
• 이를 통해 스택의 크기가 계속해서 증가하지 않고, 메모리 사용량이 증가하지 않는 장점이 있다.
• 일부 프로그래밍 언어는 꼬리 재귀 함수를 최적화하여 호출 스택을 사용하지 않도록 만들어 메모리 사용량을 최적화할 수 있다.

 

재귀호출 방법의 실행 컨텍스트의 수는 1개이다.

 

이렇게만 읽으면 이해가 안 가니 바로 예시를 들어 보겠다.

 

예를 들어,  

 

1부터 n까지의 합을 구하는 재귀 함수 

function sum(n) {
  if (n === 0) {
    return 0;
  }
  return n + sum(n - 1);
}

// 예시
sum (3) 일 때,

(1) sum(3) = 3 + sum(2) 호출                          // 메모리 누적 1 (호출 후에 실행할 코드가 남아있음)
(2) sum(2) = 2 + sum(1) 호출                          // 메모리 누적 2
(3) sum(1) = 1 + sum(0) 호출                          // 메모리 누적 3

(4) ** sum (0)은 0 이다. 즉, sum(1)은 1 (리턴)           // 메모리 누적 2
(5) sum(2) = 2 + 1 = 3   (리턴)                       // 메모리 누적 1
(6) sum(3) = 3 + 3 = 6    (리턴)                      // 메모리 누적 0

 

• 위 함수는 재귀적으로 자신을 호출하면서 스택을 쌓아가며 결과값을 계산한다. 
• 이때 스택에는 매번 함수가 호출될 때마다 실행 컨텍스트가 저장되어 메모리 사용량이 증가한다.

 

이 함수를 꼬리 재귀 형태로 바꾸면 다음과 같다.

 

1부터 n까지의 합을 구하는 꼬리 재귀 함수 

function sum(n, acc = 0) {
  if (n === 0) {
    return acc;
  }
  return sum(n - 1, acc + n);
}

// 예시
sum(3) 일 때,

(1) sum(3) = sum(2, 3) 호출                      // 메모리 누적 1 (호출 후에 더 이상 실행할 코드가 없으므로 사라짐)
(2) sum(2) = sum(1, 5) 호출                      // 메모리 누적 1  
(3) sum(1) = sum(0, 6) 호출                      // 메모리 누적 1  

(4) ** sum (0)일때  acc 값인 6을 리턴
(5) 6 리턴
(6) 6 리턴

 

• 위 함수에서 acc는 계산된 합을 저장하는 변수이다. 초기값으로 0을 설정한다. 
• 이 함수는 스택에 계속해서 쌓이지 않고, 재귀 호출을 위한 추가적인 메모리 사용이 없이도 계산이 가능하다. 
• 이를 통해 메모리 사용량이 최적화되고, 스택 오버플로우 에러를 방지할 수 있다.

 

꼬리 재귀 함수 만들기

 

• 꼬리 재귀 형태의 함수를 만들기 위해서는, 함수가 마지막에 반환하는 값이 자기 자신을 호출하는 부분이어야 한다. 
• 재귀함수의 실행 결과가 연산에 사용되지 않고 바로 반환되게 함으로써 이전 함수의 상태를 유지할 필요가 없도록 재귀 함수를 작성하는 것이 포인트다.
• 꼬리 재귀가 동작하려면 플랫폼과 컴파일러가 꼬리 물기 최적화(TCO)를 지원해줘야 한다.
  
  • ECMAScript 2015부터 'use strict'모드에서 TCO가 자동으로 적용되도록 규정되어 있다.
    • Google Chrome과 Node.js의 V8엔진은 TCO를 지원한다.
    • Mozilla Firefox의 SpiderMonkey 엔진, Microsoft Edge의 Chakra 엔진 등 최신 웹 브라우저들은 TCO를 지원한다.
    • Internet Explorer, Opera Mini 등 구형 브라우저나 일부 혹은 구형 모바일 기기에서도 지원하지 않는다.

 

다른 예시로 정리해보기

 

일반적인 재귀함수

function factorial(n) {
if (n === 1) return 1;
return n * factorial(n -1);

// 예시: factorial(3)

(1) factorial(3) = 3 * factorial(2)
(2)                    factorial(2) = 2 * factorial(1)
(3)                                       factorial(1) === 1
(4)                    factorial(2) = 2 *  1 === 2
(5) factorial(3) = 3 * 2 === 🟣 6 🟣

 

꼬리 재귀함수

function factorial(n, acc = 1) {
  if (n === 1) {
    return acc;
  }
  return factorial(n - 1, acc * n);
}

// 예시: factorial(3)

(1) factorial(3) = factorial(2, 1*3) 호출
(2) factorial(2) = factorial(1, 1*3*2) 호출   // 기존 실행 컨텍스트 덮어쓰기
(3) factorial(1) : acc(===6) 리턴             // 기존 실행 컨텍스트 덮어쓰기
(4) 6 리턴
(5) 6 리턴

 

 

• acc의 초기값으로 1을 설정한다. 
• 위의 재귀함수와 달리 반환값에서 추가 연산이 필요없다.
• 실행 컨텍스트가 덮어 쓰여졌다는 것은 기존에 있던 실행 컨텍스트의 정보들이 현재 실행 컨텍스트로 덮어 씌워진다는 의미이다.
  • 이전 실행 컨텍스트가 사라진 것은 아니며, 현재 실행 컨텍스트의 마지막 부분에서 return문을 실행하면 이전 실행 컨텍스트로 돌아가서 값을 전달한다.

 

[정리]

꼬리 재귀: 재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태 

- 꼬리 재귀를 이용하면 함수 호출이 반복되어 스택이 늘어나고 깊어지는 문제를 컴파일러가 선형으로(순차적으로) 처리하도록 알고리즘을 바꿔 스택을 재사용(갈아끼우기)할 수 있게 된다.