尾递归优化是一场谎言

TLDR

• 
  
• 本文是对蹦床函数的应用案例。
  
• 蹦床函数跟尾递归优化都是为了解决递归次数过多导致调用栈溢出的问题。
  
• 蹦床函数的原理：令原函数返回一个可执行函数，由蹦床函数来控制执行时机，使执行函数与其父函数无执行调用关系。
  
• 处理递归栈溢出还有递归转迭代、异步执行等方案，但蹦床函数对代码的改动量很低，也不影响原代码的阅读和执行逻辑。
  

起因

接到一个需求，需要对 markdown 进行分句。大致如下：

// 原始 md

aaa。bbb[^1^]。ccc。


// 转换后 md

aaa。x:[bbb[^1^]]。ccc。

即把以[^*^]结尾的句子给包起来。

方案思路比较简单：

• 
  
• 写一个函数，入参为起始位置，大概这样：walk(startIndex)。
  
• 起始位置设为最后一个字符位置，往前找，如果找到[^*^]则往前找句子结束符（如。！？-），找到后就把整句话用x:[]包起来。
  
• 继续调用这个函数，入参startIndex为刚刚那个句子的起始位置。
  
• 直到入参为0（即找到头了），结束执行。
  

完美，补充完测试用例，开心光速下班 😃。

命运所有的馈赠早已暗中标好了价格。

报错

一天后：

栈溢出了。

同事的需求需要往这段 markdown 里填充上万字符，我的递归函数爆栈了 🤯🤯🤯。

一时间脑海里立刻出现 3 条解决方案：

• 
  
• 问 gpt
  
• 问 gpt
  
• 问 gpt
  

得到了6种解决方案：

简单评估下这几个方案：

• 
  
• 方案2和3对代码的改动量较大，递归变迭代，实在懒得改也懒得验证，哒咩 ❌
  
• 方案4和5把同步逻辑改成了异步，对代码逻辑的侵入性太强，哒咩 ❌
  
• 方案1的尾递归优化我现在就在用，无效，哒咩 ❌
  

方案一让我感觉撞了鬼：为什么我写的尾递归优化没生效？

搜了下才发现尾递归优化可谓名存实亡，主流浏览器全都不支持尾递归优化：

compat-table.github.io/compat-tabl…

详见文章：尾递归的后续探究-腾讯云开发者社区-腾讯云

解决

5/6的方案都被否掉，看来看去只能使用 Trampoline 函数，即蹦床函数。

我们看下 gpt给的示例，以解释蹦床函数做了些什么：

function trampoline(fn) {
return function(...args) {
let result = fn(...args);
while (typeof result === 'function') {

      result = result();

    }
return result;

  };

}

function sum(x, y) {
if (y > 0) {
return () => sum(x + 1, y - 1);

  } else {
return x;

  }

}

let safeSum = trampoline(sum);
safeSum(1, 100000);

这里对原函数的修改在第13行，正常的递归会直接执行sum函数，而这段优化里则改成返回了一个函数，我们姑且称之为 handler 函数。

而 trampoline 函数的作用则是执行 sum 函数并判断返回值，如果返回值是函数（即 handler 函数），则继续执行该函数，直到返回值是数字。整个判断&执行过程使用 while循环。

蹦床函数之所以能够摆脱递归调用栈限制，是因为 handler 函数是由蹦床函数执行的，handler 函数执行前，它的父函数 sum 函数已经执行完毕了，handler 的执行跟 sum 的执行没有堆栈关系。

完美，

• 
  
• 补充测试用例。
  
• 加上try catch防止白屏。
  
• 加上memo防止每次render都递归计算。
  

开心光速下班 😃。