JavaScript 호출 스택, 꼬리 재귀 및 수동 최적화에 대한 자세한 소개

이 글에서는 JavaScript 호출 스택, tailrecursion 및 수동 최적화에 대한 자세한 설명을 주로 소개합니다. 관심 있는 친구들은

Call Stack(Call Stack)을 참조하세요. 스택은 기본적인 컴퓨터 개념입니다. 여기서는 스택 프레임이라는 개념을 소개합니다.

스택 프레임은

function

호출을 위해 별도로 할당된 스택 공간 부분을 나타냅니다.
실행 중인 프로그램이 현재 함수에서 다른 함수를 호출하면 다음 함수에 대한 새 스택 프레임이 생성되고 이 스택 프레임이 입력됩니다. 원래 함수에는 호출 프레임이라고 하는 해당 스택 프레임도 있습니다. 각 스택 프레임은 현재 함수의 로컬

변수

를 저장합니다.

함수는 호출 스택 상단에 추가되며, 실행이 완료된 후 해당 함수는 호출 스택 상단에서 제거됩니다. 그리고 이때 스택 맨 위에 있는 스택 프레임에 프로그램 실행 권한(프레임 포인터)을 부여합니다. 이 후입후퇴 구조는 함수의 호출 스택입니다.

JavaScript에서는 console.trace() 메소드를 통해 현재 함수의 호출 프레임을 쉽게 볼 수 있습니다

Tail call

tail recursion에 대해 이야기하기 전에 tail call이 무엇인지 먼저 이해해야 합니다. 이다. 간단히 말해서, 함수 실행의 마지막 단계는 다른 함수를 호출하고 반환하는 것입니다.

다음은 올바른 데모입니다.

// 尾调用正确示范1.0
function f(x){
 return g(x);
}

// 尾调用正确示范2.0
function f(x) {
 if (x > 0) {
  return m(x)
 }
 return n(x);
}

1.0 프로그램의 마지막 단계는 함수 g를 실행하고 동시에 해당 반환 값을 반환하는 것입니다. 2.0에서는 tail call이 실행될 때 마지막 단계인 한 마지막 줄에 작성할 필요가 없습니다.

다음은 오류 데모입니다.

// 尾调用错误示范1.0
function f(x){
 let y = g(x);
 return y;
}

// 尾调用错误示范2.0
function f(x){
 return g(x) + 1;
}
// 尾调用错误示范3.0
function f(x) {
 g(x); // 这一步相当于g(x) return undefined
}

1.0의 마지막 단계는 할당 작업이고, 2.0의 마지막 단계는 추가 작업이며, 3.0에는 정의되지 않은 암시적 반환이 있습니다.

테일 호출 최적화

In the 우리가 알고 있는 호출 스택 부분은 함수 A가 다른 함수 B를 호출하면 스택 프레임이 형성됩니다. 호출 스택에는 호출 프레임 A와 현재 프레임 B가 모두 있습니다. 이는 함수 B가 실행된 후이기 때문입니다. 완료되면 실행 권한을 A에 반환해야 하며, 함수 A 내부의 변수, 함수 B가 호출되는 위치, 기타 정보는 호출 프레임 A에 저장되어야 합니다. 그렇지 않으면 함수 B가 실행을 마치고 함수 A를 계속 실행하면 모든 것이 잘못될 것입니다.

이제 함수 A의 마지막 호출(즉, 테일 호출)에 함수 B를 넣었습니다. 함수 A의 스택 프레임을 유지해야 합니까? 물론 그렇지 않습니다. 호출 위치와 내부 변수는 다시 사용되지 않기 때문입니다. 따라서 함수 A의 스택 프레임을 함수 B의 스택 프레임으로 교체하면 됩니다. 물론 내부 함수가 외부 함수의 변수를 사용하는 경우 함수 A의 스택 프레임은 여전히 ​​유지되어야 합니다. 일반적인 예는 클로저입니다.

인터넷에는 테일콜을 설명하는 블로그 글이 많이 있는데, 가장 많이 유포되는 글 중 하나에 이런 글이 있습니다. 나는 별로 동의하지 않는다.

function f() {
 let m = 1;
 let n = 2;
 return g(m + n);
}
f();
// 等同于
function f() {
 return g(3);
}
f();
// 等同于
g(3);

다음은 블로그 원문입니다. 위 코드에서 함수 g가 tail call이 아닌 경우 함수 f는 내부 변수 m과 n의 값, g의 호출 위치, 기타 정보를 저장해야 합니다. . 하지만 함수 f는 g를 호출한 후에 종료되므로 마지막 실행 단계에서 f()의 호출 기록은 삭제하고 g(3)의 호출 기록만 보관하면 됩니다.

하지만 첫 번째 방법도 m+n 단계를 먼저 수행한 다음 g 함수를 호출하고 동시에 반환하는 것 같아요. 이것은 꼬리 호출이어야 합니다. 동시에 m+n의 값도 매개변수를 통해 함수 g에 전달되고 직접 참조되지 않으므로 f 내부의 변수 값을 저장해야 한다고 말할 수는 없습니다.

일반적으로 모든 함수 호출이 tail call이면 호출 스택의 길이도 훨씬 줄어들고, 필요한 메모리도 크게 줄어듭니다. 이것이 테일 콜 최적화의 의미입니다.

꼬리 재귀

재귀는 함수 정의에 함수

자체를 사용하는 방법을 말합니다. 자신을 호출하는 함수를 재귀(recursion)라고 하고, 마지막에 자신을 호출하는 함수를 꼬리 재귀(tail recursion)라고 합니다.

가장 일반적인 재귀, 피보나치 수열, 일반 재귀 작성 방법:

function f(n) {
 if (n === 0 || n === 1) return n 
 else return f(n - 1) + f(n - 2)
}

이 작성 방법은 간단하고 투박하지만 매우 심각한 문제를 안고 있습니다. 호출 스택은 n이 증가함에 따라 선형적으로 증가합니다. n이 큰 숫자일 때(테스트해 보니 n이 100일 때 브라우저 창이 멈춥니다...) 스택이 터질 것입니다(스택 오버플로). ). 이는 이러한 재귀 작업에서는 동시에 많은 수의 스택 프레임이 저장되고, 호출 스택이 매우 길며, 막대한 양의 메모리가 소모되기 때문입니다.

接下来，将普通递归升级为尾递归看看。

function fTail(n, a = 0, b = 1) { 
 if (n === 0) return a
 return fTail(n - 1, b, a + b)
}

很明显，其调用栈为

 代码如下:

fTail(5) => fTail(4, 1, 1) => fTail(3, 1, 2) => fTail(2, 2, 3) => fTail(1, 3, 5) => fTail(0, 5, 8) => return 5

被尾递归改写之后的调用栈永远都是更新当前的栈帧而已，这样就完全避免了爆栈的危险。

但是，想法是好的，从尾调用优化到尾递归优化的出发点也没错，然并卵：），让我们看看V8引擎官方团队的解释

Proper tail calls have been implemented but not yet shipped given that a change to the feature is currently under discussion at TC39.

意思就是人家已经做好了，但是就是还不能不给你用：）嗨呀，好气喔。

当然，人家肯定是有他的正当理由的：

1. 在引擎层面消除尾递归是一个隐式的行为，程序员写代码时可能意识不到自己写了死循环的尾递归，而出现死循环后又不会报出stack overflow的错误，难以辨别。

2. 堆栈信息会在优化的过程中丢失，开发者调试非常困难。

道理我都懂，但是不信邪的我拿nodeJs（v6.9.5）手动测试了一下：

好的，我服了

手动优化

虽然我们暂时用不上ES6的尾递归高端优化，但递归优化的本质还是为了减少调用栈，避免内存占用过多，爆栈的危险。而俗话说的好，一切能用递归写的函数，都能用循环写——尼克拉斯·夏，如果将递归改成循环的话，不就解决了这种调用栈的问题么。

方案一：直接改函数内部，循环执行

function fLoop(n, a = 0, b = 1) { 
 while (n--) {
  [a, b] = [b, a + b]
 }
 return a
}

这种方案简单粗暴，缺点就是没有递归的那种写法比较容易理解。

方案二：Trampolining（蹦床函数）

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

function f(n, a = 0, b = 1) { 
 if (n > 0) {
  [a, b] = [b, a + b]
  return f.bind(null, n - 1, a, b)
 } else {
  return a
 }
}

trampoline(f(5)) // return 5

这种写法算是容易理解一些了，就是蹦床函数的作用需要仔细看看。缺点还有就是需要修改原函数内部的写法。

方案三：尾递归函数转循环方法

function tailCallOptimize(f) { 
 let value
 let active = false
 const accumulated = []
 return function accumulator() {
  accumulated.push(arguments)
  if (!active) {
   active = true
   while (accumulated.length) {
    value = f.apply(this, accumulated.shift())
   }
   active = false
   return value
  }
 }
}

const f = tailCallOptimize(function(n, a = 0, b = 1) { 
 if (n === 0) return a
 return f(n - 1, b, a + b)
})
f(5) // return 5

经过 tailCallOptimize 包装后返回的是一个新函数 accumulator，执行 f时实际执行的是这个函数。这种方法可以不用修改原递归函数，当调用递归时只用使用该方法转置一下便可解决递归调用的问题。

总结

尾递归优化是个好东西，但既然暂时用不上，那我们就该在平时编码的过程中，对使用到了递归的地方特别敏感，时刻避免出现死循环，爆栈等危险。毕竟，好的工具不如好的习惯。

위 내용은 JavaScript 호출 스택, 꼬리 재귀 및 수동 최적화에 대한 자세한 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!