递归与尾递归

在介绍递归与尾递归之前,我们来看看递归的定义:程序调用自身的编程技巧称为递归( recursion)

百度对递归的定义:递归

接着,我们再来看看一道题

编写一个函数fn,接收一个或者多个参数,其中一个参数为n,若 n=0 或者 n=1,函数返回 1, 否则函数返回 1+2+3+...+(n-1)+n 的总和

递归

按照我们一般的思维,很快就能想到使用递归函数来解决这个问题,所以来看看递归是怎么解决的呢

function fn(n){
 if( n === 0 || n === 1 ){
   return 1
 }
 return n + fn(n - 1)
}

如果 n=5 那么上面的函数运行流程

n = 5 ==> 5 + fn(5 - 1)
n = 4 ==> 5 + 4 + fn(4 - 1)
n = 3 ==> 5 + 4 + 3 + fn(3 - 1)
n = 2 ==> 5 + 4 + 3 + 2 + fn(2 - 1)
n = 1 ==> 5 + 4 + 3 + 2 + 1

即:最后的结果是 5 + 4 + 3 + 2 + 1 = 15

可以看到,一般的递归,每一级递归都需要调用函数,同时这个函数还与其他的表达式运算,那这样的递归每一次都会创建新的栈。

随着递归深度的增加,创建的栈越来越多,最终造成爆栈

所以,递归虽然可以解决很多问题,但是也需要注意一下使用限制。

#尾递归 如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。

百度定义:尾递归

尾递归基于函数的尾调用(尾调用:返回一个函数并且调用这个函数), 每一级调用直接返回函数的返回值更新调用栈,而不用创建新的调用栈, 类似迭代的实现, 时间和空间上均优化了一般递归!

同样的问题,使用尾递归的来看看

function fn(n, total = 1){
  if(n === 1 || n === 0){
    return total
  }
  return fn(n -1, total + n)
}

同样是 n=5,来看看运行过程

n = 5 ==> fn(5, 1)
n = 4 ==> fn(4, 6)
n = 3 ==> fn(3, 10)
n = 2 ==> fn(2, 13)
n = 1 ==> fn(1, 15)

上面的运行每一次都是返回的一个单独的函数,没有其他的表达式与这个函数的结果运行,每一级递归的函数调用变成”线性”的形式。

上面就是关于一般递归与尾递归的说明。但是这里存在一个很大的问题,那就是JavaScript的 V8引擎 对尾递归的优化做的并不好,上面的代码尾递归还不如一般的递归。虽然在JavaScript中无法运行,但是其他的语言例如Java,C,C++等,使用尾递归的好处多余一般递归。

手动优化

既然我们在JavaScript中无法使用尾递归,使用递归也害怕爆栈,那我们可以自己来一些方法实现相同的效果,例如上面的多个值相加

方案一:修改函数内部,使用循环

// n 是 正整数
function fn(n, a=0, b=1){
  while (n--) {
    [a, b] = [b, a + b]
  }
  return a
}

这个方法采用了ES6中解构赋值。如果你不了解结构复制,可以去看看,如果你了解结构复制,那么上面的你就很容易理解了。

其实这种优化方法就是支持尾递归运行的这些引擎对相应语言的优化,使用循环优化,只是JavaScript V8 中没有相应的优化。说白了,就是想Java等语言已经有人帮你做了这一步。

方案二:蹦床函数

这是上面的尾递归的变形

// 尾递归代码
function fn(n, total = 1){
  if(n === 1 || n === 0){
    return total
  }
  return fn(n -1, total + n)
}

这里我们来求一下 n=3 的时候的值,如果是使用尾递归,那么 n = 3 ==> 6

首先来了解一下什么是蹦床函数,先来看一段代码

function fn(n, total = 1){
  if(n === 1 || n === 0){
    return total
  }
  return function(){
    return fn(n -1, total + n)
  }
}

同样是 n=3

// n = 3
fn(3) ==> Function
fn(3)() ==> Function
fn(3)()() ==> 6

从上面可以看到,如果 n 不是3而是一个很大的数字,那么我们就需要调用很多次函数调用来实现。为了简便,我们可以把这种调用形式写成函数,这样的函数就是蹦床函数

// 蹦床函数
function trampoline(func, n){
  let result = func.call(func, n)
  while ( typeof result === 'function' ){
    result = result()
  }
  return result
}

这个蹦床函数有两个参数,第一个参数是一个函数,即我们需要实现逻辑的函数,本例中就是

function fn(n, total = 1){
  if(n === 1 || n === 0){
    return total
  }
  return function(){
    return fn(n -1, total + n)
  }
}

使用蹦床函数代码耗时相对较长。

以上就是关于递归与尾递归的说明以及优化,当然,如果你要更好的方案,欢迎在评论区留言。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户1052078的专栏

Jenkins安装 基于宝塔面板

点开Java项目管理器,在版本管理中安装tomcat8,这个版本安装的jdk是1.8版本的。

12330
来自专栏刷题笔记

7-15 删除字符串中的子串 (20 分)转角做对一道题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

31930
来自专栏Don的成长史

【PAT乙级】科学计数法

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

9220
来自专栏腾讯开源的专栏

微服务云原生等场景,腾讯 Kona JDK 正式开源

? Tencent Kona 是基于 OpenJDK8,由腾讯专业技术团队提供技术维护、优化及安全保障的 JDK 产品。腾讯的 Java 应用场景丰富,结合微...

18640
来自专栏刷题笔记

【java入门】01配置环境变量

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

9630
来自专栏Java知己

Java 8:一文掌握 Lambda 表达式

能够使用 Lambda 表达式的一个重要依据是必须有相应的函数接口。所谓函数接口,是指内部有且仅有一个抽象方法的接口。

6730
来自专栏笔记1

docker的一些命令

docker create --name myrunoob nginx:latest

6410
来自专栏未读代码的专栏

设计模式 -创建型模式之单例模式的五种实现

许多时候整个系统只需要拥有一个的全局对象,这样有利于我们协调系统整体的行为。比如在某个服务器程序中,该服务器的配置信息存放在一个文件中,这些配置数据由一个单例对...

6130
来自专栏用户1052078的专栏

宝塔环境 搭建多java站点配置

java程序分为2种类型,一种是Springboot,打包方式为jar文件,内置了tomcat,另一种方式war打包,这个会自动解压文件。 文章只做了jar文...

15040
来自专栏全栈前端精选

我的前端成长之路

注:这是在阿里内部前端大学的一个分享,整理了一份对外的版本,希望分享内容能对你有所帮助。

8110

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励