见识一下尾递归的强大,尾递归怎么会比迭代

发布网友发布时间：2022-04-29 15:32

共1个回答

热心网友时间：2022-04-22 17:29

TCO，tail-call optimization，其实有多种解读方式。
最常见的解读方式是：对于尾调用的函数调用，不要浪费栈空间，而要复用调用者的栈空间。这样的结果就是一长串尾调用不会爆栈，而没有TCO的话同样的调用就会爆栈。
从这个意义上说，题主贴的那个recipe确实达到了TCO的部分目的：

通过stack introspection查看调用链上的调用者之中有没有自己
有的话，通过抛异常来迫使栈回退（stack unwind）到之前的一个自己的frame
在回退到的frame接住异常，拿出后来调用的参数，用新参数再次调用自己
这样就可以让尾递归不爆栈。但这样做性能是没保证的…而且对于完全没递归过的一般尾调用也不起作用。
一种对TCO的常见误解是：由编译器或运行时系统把尾调用/尾递归实现得很快。这不是TCO真正要强调的事情——不爆栈才是最重要的。也就是说其实重点不在“优化”，而在于“尾调用不爆栈”这个语义保证。
“proper tail-call”的叫法远比“tail-call optimization”来得合适。
因而像题主说的那种做法，可以算部分TCO，但算不上“性能优化”意义上的优化。