JavaScript - 用大白话理解递归的本质

巴拉米
• 阅读 1248

先来个场景:

下班了,你带着女友去电影院看电影~(没有女友?快私信我,组里各种白富美!加班没时间?快私信我,组里加班少!)
女友问,咱两现在坐在第几排啊?电影院里面太黑了,看不清,没法数,现在你怎么办?

于是你开始展示你智慧的一面了,先问前排的人他是第几排,你想只要在他的数字上加一,就知道自己在哪一排了。

但是,前面的人也看不清啊,所以他也问他前面的人。就这样一排一排往前问~ 直到问到第一排的人,说我在第一排,然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排,于是你就知道答案了。

这就是一个非常标准的递归求解问题的分解过程,去的过程叫“递”,回来的过程叫“归”,所以叫“递归”。

递归的本质:将原来的问题,转化为更小的同一问题。问题一点点变小,当问题变成最小级别之后,先解决最小级别的问题的答案,然后大一点的问题也有了答案,一点点的往上,这样原来的问题也就有了答案~

举例理解递归:数组求和

举个代码的例子理解下递归:对数组求和。

假设对 [1,2,3,4]求和,可以转化为 [2,3,4]的求和,这样问题就变得更小,直到转为空数组,空数组就是最小级别的问题,先解决最小级别的问题,然后大一点的问题也有了答案,一点点的,这样原来的问题也就有了答案~

伪代码:

=> [1,2,3,4]  
=> [1,2,3,4] = 1 + [2,3,4]  
=> [2,3,4] = 2 + [3,4]  
=> [3,4] = 3 + [4]  
=> [4] = 4 + []  
=> [] = 0  
=> [4] = 4 + 0  
=> [3,4] = 3 + 4  
=> [2,3,4] = 2 + 7  
=> [1,2,3,4] = 1 + 9  
=> 解决  

写真实的代码:

function sum(arr) {  
  // 先解决最小级别的问题  
  if (arr.length === 0) {  
    return 0;  
  }  
  // 大的问题 转化为 更小的问题  
  return arr[0] + sum(arr.slice(1));  
}  

可视化递归过程

上面看完之后,可能还是有点点蒙圈,感觉似懂非懂~

没事,可视化代码运行,就明白了!可视化的过程,也是调试的技巧!

先可视化上面的数组求和:

function sum(arr, depth) {  
  // 递归层级越深,缩进越长。同一层级的,缩进等长  
  const indent = "--".repeat(depth);  
  // 调用开始,输出一次  
  console.log(`${indent}Start Call: sum of [${arr}]`);  
  if (arr.length === 0) {  
    const res = 0;  
    // 返回之前,输出一次  
    console.log(`${indent}Return: sum of [${arr}] is ${res}`);  
    return res;  
  }  
  let res = sum(arr.slice(1), depth + 1);  
  // 调用之后,输出一次  
  console.log(`${indent}After Call: sum of [${arr.slice(1)}],sum is ${res}`);  
  res = arr[0] + res;  
  // 返回之前,输出一次  
  console.log(`${indent}Return: sum of [${arr}] is ${res}`);  
  return res;  
}  
sum([1, 2, 3, 4], 0);  

执行代码:

Start Call: sum of [1,2,3,4]  
--Start Call: sum of [2,3,4]  
----Start Call: sum of [3,4]  
------Start Call: sum of [4]  
--------Start Call: sum of []  // 这里是最小级别的问题  
--------Return: sum of [] is 0 // 解决最小级别的问题  
------After Call: sum of [],sum is 0  
------Return: sum of [4] is 4  
----After Call: sum of [4],sum is 4  
----Return: sum of [3,4] is 7  
--After Call: sum of [3,4],sum is 7  
--Return: sum of [2,3,4] is 9  
After Call: sum of [2,3,4],sum is 9  
Return: sum of [1,2,3,4] is 10  

再联系本文开头的话,“递”和“归”的过程,就能看出来了~

大问题转化为更小的同一问题,一直转化到最小级别的问题,先解决最小级别的问题,然后大一点的问题就解决了,一直到原先的问题就会被解决~

可视化代码的步骤:

  • 先给函数加个额外的参数:递归深度,表示递归到哪了

  • 递归深度,可以用字符串缩进可视化

  • 调用开始的时候,打印下当前的参数(可语义下)

  • 调用之后,打印下调用返回的结果和对应参数(可语义下)

  • 返回结果之前,打印下返回结果和对应参数(可语义下)

怎么写递归

两步:

  • 找到递归边界:找到最小级别的问题,并搞定答案

  • 找到递归式:将大问题转化为更小的同一问题(假设更小的问题有了答案,只想到第一层就行)

再举个例子:

有一组数:1,1,2,3,5,8,13,21........

问第 n 个数是什么?

细细看看,其实就是斐波拉契数列,后面一个数等于前两数之和。

  • 找到递归边界:找到最小级别的问题,并搞定答案

其实就是前两个数:

f(1) = 1;  
f(2) = 1;  
  • 找到递归式:将大问题转化为更小的同一问题(假设更小的问题有了答案,只想到第一层就行)

第 n 个数就是前两数之和:

f(n) = f(n - 1) + f(n - 2);  

撸码:

function f(n) {  
  // 最小级别的问题,务必搞定答案  
  if (n === 1) return 1;  
  if (n === 2) return 1;  
  // 假设n-1和n-2都知道的话  
  return f(n - 1) + f(n - 2);  
}  

可以试试可视化过程,这里我就不演示了,当作业了~

递归的缺陷和解决方案

两个大缺陷:

  • 堆栈溢出

  • 重复计算度高

可以看到,递归的过程就是函数调用的过程,反复调用函数,函数调用栈会很高,一定数量级之后,会溢栈,专业名词就是堆栈溢出,表现为代码报错了!

这种缺陷的一个解决办法是:提前规定最大深度,超过深度之后直接报错。
当然这个最大深度不一定好估计。

// 全局变量,表示递归的深度。  
let depth = 0;  

function f(n) {  
  ++depth;  
  if (depth > 1000) throw Error('递归层次超过范围了');  
  if(n === 1) return 1  
  if(n === 2) return 1  
  return f(n-1) + f(n-2)  
}  

重复计算度高怎么理解呢?

比如计算第 5 个数,等价于 f(3)+f(4),而f(4)等价于f(3)+f(2),注意这里的 f(3)出现了两次,这还只是计算第 5 个数,如果更大的话,会重复计算更多次!

这种缺陷的一个解决办法是:用哈希表保存已经求解过的 f(k),调用到 f(k) 时,哈希表有则直接返回,不需要重复计算了。当然代价是,空间复杂度变高。

let resolvedList = {};  

function f(n) {  
  if (n === 1) return 1;  
  if (n === 2) return 1;  
  // 保存过的话直接返回  
  if (resolvedList[n]) {  
    return resolvedList[n];  
  }  
  const res = f(n - 1) + f(n - 2);  
  // 没保存过的,保存下  
  resolvedList[n] = res;  
  return res;  
}  

除了堆栈溢出、重复计算度这两个大问题,时间上,过多的函数调用会积聚成一个可观的时间成本;空间上,调用一次就会在内存栈中保存一次现场数据,同样也会有可观的空间成本。

怎么将递归代码改写为非递归代码

递归的好处是代码简洁易理解,坏处就是上面的。能不能将其转化为非递归代码呢?答案是肯定的!递归的过程可以理解为函数调用栈的过程,我们可以手动模拟进栈出栈,也就是迭代循环!

// 数组求和:  
/*  
function sum(arr) {  
  if (arr.length === 0) return 0;  
  return arr[0] + sum(arr.slice(1));  
}  
*/  
function sum(arr) {  
  if (n === 0) return 0;  
  let res = 0;  
  for (let i = 0; i <= arr.length; i++) {  
    // 手动迭代res  
    res = arr[i] + res;  
  }  
}  
// 斐波拉契数列:  
/*  
function f(n) {  
  if (n === 1) return 1;  
  if (n === 2) return 2;  
  return f(n - 1) + f(n - 2);  
}  
*/  
function f(n) {  
  if (n === 1) return 1;  
  if (n === 2) return 1;  

  let res = 0;  
  let pre = 1;  
  let prepre = 1;  
  for (let i = 3; i <= n; ++i) {  
    // 手动迭代res  
    res = pre + prepre;  
    prepre = pre;  
    pre = res;  
  }  
  return res;  
}  

“手动”递归,并不是说没有缺点,虽然没有那么多函数调用,但是重复计算度依然很高。另外,迭代循环,对于线性结构的还好理解些,对于非线性结构的理解起来会更困难。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Karen110 Karen110
2年前
一篇文章带你了解JavaScript日期
日期对象允许您使用日期(年、月、日、小时、分钟、秒和毫秒)。一、JavaScript的日期格式一个JavaScript日期可以写为一个字符串:ThuFeb02201909:59:51GMT0800(中国标准时间)或者是一个数字:1486000791164写数字的日期,指定的毫秒数自1970年1月1日00:00:00到现在。1\.显示日期使用
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Easter79 Easter79
2年前
swap空间的增减方法
(1)增大swap空间去激活swap交换区:swapoff v /dev/vg00/lvswap扩展交换lv:lvextend L 10G /dev/vg00/lvswap重新生成swap交换区:mkswap /dev/vg00/lvswap激活新生成的交换区:swapon v /dev/vg00/lvswap
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Karen110 Karen110
2年前
​一篇文章总结一下Python库中关于时间的常见操作
前言本次来总结一下关于Python时间的相关操作,有一个有趣的问题。如果你的业务用不到时间相关的操作,你的业务基本上会一直用不到。但是如果你的业务一旦用到了时间操作,你就会发现,淦,到处都是时间操作。。。所以思来想去,还是总结一下吧,本次会采用类型注解方式。time包importtime时间戳从1970年1月1日00:00:00标准时区诞生到现在
Easter79 Easter79
2年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
2个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这