朋友你听说过尾递归吗

1. 尾递归

说起尾递归就不能不提一下尾调用(Tail Call)

尾调用:在函数的最后一步调用另外一个函数。

function func(){
    // ... other code
    return otherFunc();// 尾调用
}

尾递归:在函数的最后一步调用自身

function func(){
    // ... other code
    return func();// 尾递归
}

2. 尾调用和非尾调用

说到递归,那就必然要以斐波那契数列为例子

斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……

简单的说,斐波那契数列中的每一项都是前两项的和。 即F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>2,n∈N*)

2.1 常见版本

// 实现出来长这样
function fibo(n) {
    if (n <= 0) {
        return 0;
    } else if (n === 1) {
        return 1;
    }
    return fibo(n - 1) + fibo(n - 2)
}

所以手动模拟一下计算fibo(5)的调用栈,大概是这样的

fibo(5)
fibo(4) + fibo(3)
fibo(3) + fibo(2)+  fibo(3)
fibo(2) + fibo(1) + fibo(2)+  fibo(3)
2 + fibo(2) +  fibo(3)
3 + fibo(3)
3 + fibo(2) + fibo(1)
3 + 2
5

在计算的过程中,堆栈需要不停的记录每一层次调用的详细信息(如参数、局部变量、返回地址等等),以确保该层次的操作完成,能返回到上一层次,这些信息再少也会占用一定空间,成千上万个此类空间累积起来,自然就超过线程的栈空间了。于是stackOverflow异常就被抛出了。

2.2 尾递归版本

function fibo(n, num1 = 1, num2 = 1) {
    if (n <= 0) {
        return 0;
    } else if (n === 1) {
        return num1;
    }
    return fibo4(n - 1, num2, num1 + num2);
}

同样手动模拟一下调用栈

fibo(5)
fibo(4, 1, 2)
fibo(3, 2, 3)
fibo(2, 3, 5)
fibo(1, 5, 8)

你会发现,尾调用作为函数的最后一步操作,它在某些场景下不需要保存外层函数的调用记录,因为这些信息不会再被用到了(这里是作为参数传入下一次调用了),所以可以以上层调用帧作为尾调用的调用环境。 即

fibo(5);
// 等同于调用
fibo(1, 5, 8);// 中间的调用帧都不需要保存

使用尾递归,取消过多的堆栈记录,而只记录最外层和当前层的信息,完成计算后,立刻返回到最上层。这也就不会有栈溢出的问题,同时减少了内存以及上下文切换的损耗。

细心的朋友也发现了,尾递归的本质实际上就是将方法需要的上下文通过方法的参数传递进下一次调用之中,以达到去除上层依赖。

但是这同样会引入一些让使用者费解的调用参数,上文使用ES6的默认参数解决调用暴露函数列表的问题,但是依旧可能因为用户多传入的参数导致计算结果不正确。所以你可能需要一些其他的手段解决API的问题,例如封装一层调用方法,函数柯理化等。

3. 性能对比

// 常规递归写法
function fibo(n) {
    if (n <= 0) {
        return 0;
    } else if (n === 1) {
        return 1;
    }
    return fibo(n - 1) + fibo(n - 2)
}

// 常规循环写法
function fibo2(n) {
    if (n <= 0) {
        return 0;
    } else if (n === 1) {
        return 1;
    }
    let x = 0,
        y = 1,
        sum = 0;
    for (let i = 2; i <= n; i++) {
        sum = x + y;
        x = y;
        y = sum;
    }
    return sum;
}

// 公式法
function fibo3(n) {
    if (n <= 0)
        return 0;
    else {
        const sqrtFive = Math.sqrt(5);
        const res = (Math.pow(0.5 + sqrtFive / 2, n) - Math.pow(0.5 - sqrtFive / 2, n)) / sqrtFive;
        return Math.round(res);
    }
}

// 尾递归写法
function fibo4(n, num1 = 1, num2 = 1) {
    if (n <= 0) {
        return 0;
    } else if (n === 1) {
        return num1;
    }
    return fibo4(n - 1, num2, num1 + num2);
}

function test() {
    let tick = Date.now();
    console.log(fibo(50), Date.now() - tick);
    tick = Date.now();
    console.log(fibo2(500), Date.now() - tick);
    tick = Date.now();
    console.log(fibo3(500), Date.now() - tick);
    tick = Date.now();
    console.log(fibo4(500), Date.now() - tick);
    tick = Date.now();
}

运行结果:

通过运行结果我们可以得到一些结论:

  • 慎用直接递归的方式,不仅会带来极差的运行效率,同时会导致浏览器直接无响应。在浏览器环境中,一些代价高昂的计算会导致糟糕的用户体验,因为一个页面的用户界面无响应多数是由于在运行js代码。
  • 尾递归有着与循环同样优秀的计算性能,使用尾递归可以同时拥有着循环的性能以及递归的数学表达能力

4. 一个栈溢出的例子

// 计算1-N的累加值
function f(n) {
    if (n <= 1) {
        return 1;
    }
    return f(n - 1) + n;
}
f(100000);

调用结果:

// 计算1-N的累加值(尾递归)
function f(n, sum = 1) {
    if (n <= 1) {
        return sum;
    }
    return f(n - 1, sum + n);
}
f(100000);

调用结果:

什么鬼,说好的尾递归优化呢?

5. PTC与STC

ES6标准规定了 尾调用不会创建额外的调用帧。 在严格模式下 尾调用不会造成调用栈溢出。 Proper Tail Calls(PTC)已经实现了,但是还未部署,该功能仍然在TC39标准委员会中讨论。

5.1 PTC存在的问题

  • 1 性能

大部分实现者和开发者认为PTC是一种优化策略,使得代码跑的更快。但是可能由于其他的约束,例如兼容以前的功能或顺应标准,部分团队在实现的时候牺牲了性能。

  • 2 开发者工具

在PTC的实现中,许多调用帧都被抛弃了,导致很难再调用栈中调试他们的代码。

// 举个例子
function foo(n) {
  return bar(n*2);// 尾调用
}

function bar() {
  throw new Error();
}

foo(1);
// 由于尾调用优化
// 在Error.stack或者开发者工具中,foo的调用帧被丢掉了。
  • 3 Error.stack

启用PTC导致Javascript异常有了不一致的error.stack信息。

/*
output without PTC
Error
    at bar
    at foo
    at Global Code

output with PTC (note how it appears that bar is called from Global Code)
Error
    at bar
    at Global Code
*/
  • 4 开发者意图

开发者是否真的从PTC中受益了呢,或许开发者根本就不想自动对尾调用进行优化呢?接下来讲到的STC即可避免其他事情重构的危险,有着更明确的语义。

5.2 STC

语义上的尾调用(Syntactic Tail Call)是针对上述PTC的问题而提出的建议。 STC采用类似于 return continue 的语法来明确标识出要进行尾调用优化,而在非尾调用的场景下使用该语法会抛出语法错误异常。 该语法有三种实现形式:

  • 语法级
function factorial(n, acc = 1) {
  if (n === 1) {
    return acc;
  }

  return continue factorial(n - 1, acc * n)
}
  • 函数级
#function() { /* all calls in tail position are tail calls */ }
  • 表达式/调用点
function () { 
    !return expr 
}

更多内容可参考:proposal-ptc-syntax

6. 那么问题来了

挖掘机技术 ... 呸。

我们以斐波那契数列为例子讲解了尾递归的运用方式,并对比了普通递归与尾递归的性能。

通过实验我们能够确定尾递归调用确实帮助我们调优了程序性能(第三节内容),但是通过第四节的实验我们发现依旧不能避免调用栈溢出的问题,而ES6的标准里面规定了尾调用的优化中是不会创建新的调用帧的。

那么尾递归的方式依旧出现了调用栈溢出的原因究竟是什么呢?

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法与数据结构

利用代码计算原码,反码和补码

913
来自专栏企鹅号快讯

编写高效简洁代码的那些招式1

高效的代码,每期都会给大家介绍一下编码的技巧,让我们代码更整洁更高效。我们会从python 语言切入,讲一讲如何写的代码更pythonic 。Pythonic ...

1686
来自专栏漏斗社区

CTF| 这是一个刚挖好的洞······

背景 近期在研究学习变量覆盖漏洞的问题,于是就把之前学习的和近期看到的CTF题目中有关变量覆盖的题目结合下进一步研究。 通常将可以用自定义的参数值替换原有变...

3748
来自专栏MasiMaro 的技术博文

Windows平台下的内存泄漏检测

在C/C++中内存泄漏是一个不可避免的问题,很多新手甚至有许多老手也会犯这样的错误,下面说明一下在windows平台下如何检测内存泄漏。 在windows平...

912
来自专栏小樱的经验随笔

汇编语言第三版答案(王爽)

汇编语言答案(王爽)  此文只是用来存个档,不喜勿喷 检测点1.1 (1)1个CPU的寻址能力为8KB,那么它的地址总线的宽度为 13位。 (2)1KB的存储器...

35411
来自专栏Java 源码分析

LinkedHashSet 源码分析

LinkedHashSet 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE ...

3347
来自专栏Felix的技术分享

《一个操作系统的实现》笔记(2)--保护模式

1998
来自专栏cloudskyme

跟我一起数据挖掘(21)——redis

什么是Redis Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。从2...

3406
来自专栏java一日一条

2017年高频率的互联网校园招聘面试题

参加了2017年校招,面试了阿里、百度、腾讯、滴滴、美团、网易、去哪儿等公司,个人是客户端 Android 方向,总结了面试过程中频率出现较高的题目,希望对大家...

1122
来自专栏老九学堂

2016计算机二级Java考试真题大放送,还不快收藏!

1、[单选题] 在软件开发中,需求分析阶段可以使用的工具是(  )。 A.N-S图 B.DFD图 C.PAD图 D.程序流程图 参考答案:B 参考解析:在软...

2924

扫码关注云+社区