자바스크립트 테일 재귀

1. 꼬리 재귀 사용
2. JavaScript에서 꼬리 재귀를 구현하는 방법

꼬리 재귀는 자신이 수행하는 마지막 작업을 호출하는 함수를 포함하는 프로그래밍 개념입니다. 이는 함수가 호출될 때마다 새 스택 프레임을 생성하는 대신 스택 프레임을 재사용할 수 있도록 하므로 특정 알고리즘을 최적화하는 데 유용한 기술이 될 수 있습니다.

이렇게 하면 프로그램이 사용하는 메모리 양을 줄이고 성능을 향상시킬 수 있습니다.

JavaScript에서 꼬리 재귀는 기본적으로 지원되지 않지만 다양한 기술을 사용하여 이를 달성하는 몇 가지 방법이 있습니다. 꼬리 재귀가 무엇인지, 어떻게 작동하는지, JavaScript에서 어떻게 구현하는지 자세히 살펴보겠습니다.

꼬리 재귀 사용

꼬리 재귀가 특정 상황에서 유용할 수 있는 몇 가지 이유가 있습니다.

1. 메모리 효율성: 함수가 자신을 재귀적으로 호출하면 호출할 때마다 새 스택 프레임이 생성됩니다. 이는 특히 깊게 중첩된 재귀 호출의 경우 많은 메모리를 사용할 수 있습니다.

   꼬리 재귀를 사용하면 함수가 스택 프레임을 재사용하여 프로그램에서 사용하는 메모리 양을 줄일 수 있습니다.

2. 성능: 테일 재귀는 함수가 여러 스택 프레임을 생성하고 파괴하는 오버헤드를 피할 수 있도록 하므로 성능 측면에서도 더 효율적일 수 있습니다. 이렇게 하면 특히 입력 값이 큰 경우 함수 실행 속도가 빨라질 수 있습니다.

3. 코드 단순성: 꼬리 재귀를 사용하면 명시적 루프나 반복 구조가 필요하지 않으므로 코드를 더 쉽게 이해할 수 있습니다. 이것은 코드를 더 간결하고 읽기 쉽게 만들 수 있습니다.

JavaScript에서 꼬리 재귀를 구현하는 방법

앞에서 언급했듯이 JavaScript는 기본적으로 꼬리 재귀를 지원하지 않습니다. 그러나 다양한 기술을 사용하여 이를 달성하는 몇 가지 방법이 있습니다.

예 1

한 가지 접근 방식은 함수 인수에 ES6 구문을 사용하는 것입니다. 이를 통해 함수 매개변수에 대한 기본값을 지정할 수 있습니다. 꼬리 재귀를 처리하는 간단한 래퍼 함수를 구현하는 데 사용할 수 있습니다.

function factorial(n, result = 1) {
  if (n === 1) {
    return result;
  } else {
    return factorial(n - 1, n * result);
  }
}
console.log('Factorial of 5 is ' + factorial(5));

출력:

Factorial of 5 is 120

이 예에서 result 매개변수에는 1의 기본값이 지정되어 있으므로 함수가 호출될 때 지정하지 않으면 1로 기본 설정됩니다. 이를 통해 result 매개 변수가 1로 설정된 factorial을 호출하는 간단한 래퍼 함수를 생성할 수 있습니다. 이 함수는 꼬리 재귀를 처리합니다.

예 2

또 다른 접근 방식은 현재 실행 중인 함수를 참조하는 arguments.callee 속성을 사용하는 것입니다. 아래와 같이 수행하는 마지막 작업으로 자신을 호출하는 재귀 함수를 구현하는 데 사용할 수 있습니다.

function factorial(n) {
  if (n === 1) {
    return 1;
  } else {
    return n * arguments.callee(n - 1);
  }
}
console.log('Factorial of 5 is ' + factorial(5));

출력:

Factorial of 5 is 120

이 접근 방식은 효과가 있지만 몇 가지 단점이 있습니다. 먼저 arguments.callee 속성은 엄격 모드에서 더 이상 사용되지 않으므로 코드에서 엄격 모드를 사용하는 경우 이를 사용하면 문제가 발생할 수 있습니다.

둘째, arguments.callee 속성을 다른 코드로 덮어쓸 수 있으며 이로 인해 예기치 않은 동작이 발생할 수 있습니다.

예 3

세 번째 접근 방식은 재귀 함수를 래핑하고 꼬리 재귀 방식으로 호출할 수 있는 고차 함수인 트램폴린 함수를 사용하는 것입니다. 트램폴린 기능을 구현하려면 다음 패턴을 사용할 수 있습니다.

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}

function factorial(n, result = 1) {
  if (n === 1) {
    return result;
  } else {
    return () => factorial(n - 1, n * result);
  }
}
console.log('Factorial of 5 is ' + trampoline(factorial(5)));

출력:

Factorial of 5 is 120

이 예에서 factorial 함수는 꼬리 재귀 방식으로 작성되며 재귀 호출은 함수가 반환되기 전에 수행되는 마지막 작업입니다. 그런 다음 trampoline 함수는 factorial 함수를 래핑하고 재귀 호출을 처리하여 꼬리 재귀 방식으로 factorial을 호출할 수 있도록 합니다.

트램폴린 기능을 사용하는 것은 다른 접근 방식보다 조금 더 복잡할 수 있지만 더 효율적이고 오류가 덜 발생한다는 장점이 있습니다.