当前位置：首页 > 编程日记 > 正文

Javascript函数之深入浅出递归思想，附案例与代码！

编程日记 2024-12-06 11:00:00

作者 | 浮世万千吾爱有三

责编 | Carol

来源 | CSDN 博客

递归函数的理解

1、生活中的递归

“递归”在生活中的一个典例就是“问路”。如图小哥哥进入电影院后找不到自己的座位，问身边的小姐姐“这是第几排”，小姐姐也不清楚便依次向前询问，问至第一排的观众后依次向后反馈结果，“我是第一排”，“我是第二排”，···，最终确定自己座位所在排数。

在这个过程中充分反应了“传递”（询问）和“回归”（反馈）的思想，故将这种现象称为“递归”。

2、编程中的递归

计算机有两个特点：“很笨”又“很快”。所以将“复杂问题”转化为“多步骤的简单问题”后，计算机才能高效执行。

而递归是编程算法的一种，通过调用自身，将一些复杂的问题简单化，便于得出解决方案。

下面通过简单的案例了解编程中的递归

案例：计算1+2+3+4+5+6的和。

function fn(n){if(n === 1){return 1;}return n + fn(n - 1);
}
fn(6);

计算过程：
f(6) = 6 + f(5)
f(6) = 6 + 5 + f(4)
f(6) = 6 + 5 + 4 + f(3)
f(6) = 6 + 5 + 4 + 3 + f(2)
f(6) = 6 + 5 + 4 + 3 + 2 + f(1)
f(6) = 6 + 5 + 4 + 3 + 2 + 1

由上可知递归函数的本质：

调用自身

递归函数的实现有两个要素：

终止条件
逐步靠近终止条件

案例中的终止条件是：当 n === 1 时，fn(1) === 1。若没有终止条件，函数会继续计算f(0) 、f(-1) 、f(-2) ··· 从而进入死循环，无法得出结果。

通过计算过程可以看出，函数依次计算f(6)、f(5)、f(4)、f(3)、 f(2)、f(1)，很好的满足了第二个要素逐步靠近终止条件。

递归函数的使用

通过以上讲解，想必已经了解递归函数的原理，

那么递归函数是如何写出来的呢？

如何利用递归函数解决实际问题呢？

实例探索递归函数的书写“套路”

例题：计算n的阶乘。

步骤 1：找到终止条件，写给 if

数学知识：n! = n * (n - 1) * (n - 2) * (n -3) * ··· * 3 * 2 * 1

‍

显然终止条件是 n === 1; 时， return 1;

故可以完成函数的前半部分:

function fn(n){if(n === 1){return 1;}// 未完待续
}

步骤2：找到函数的等价关系式，写给 return

数学知识：n! = n * (n - 1)!

通过数学知识 n! = n * (n - 1)! 和递归函数的本质（调用自身），
可以得出函数的等价关系式为 f(n) = n * f(n - 1);

从而可以完成函数的后半部分:

function fn(n){if(n === 1){return 1;}return n * fn(n - 1);
}

至此简单的递归函数便写出来了，递归函数最大的特点便是代码简洁（简洁到让人心虚）。

总结，递归函数的书写“套路”

1.找到终止条件，写给 if

2.找到函数的等价关系式，写给 return

递归函数的问题

想必你会说，上面的两个例题用循环就能轻松写出来，为何还需要使用递归呢？

其实能用递归解决的问题，用循环也能解决！而且递归比循环的运算速度要慢，因为递归需要逐层调用函数，占据系统内存，当递归层级较深时，对性能消耗较大，往往不推荐使用。

问：那递归存在的意义是什么？

递归是为了将复杂问题简单化，提供解题思路，进而得到 “循环算法”

对于简单问题，一眼便能看出“循环算法”，但对于抽象问题，通常可以先采取递归思想，如：

例题：某人需要走上10级台阶，有两种走法，走法A：一步1个台阶；走法B：一步2个台阶。两种走法可以任意交替使用，问走上10级台阶共有多少种方法？

‍

这个问题很难直接看出循环的解题思路，我们不妨从递归的角度尝试解决：

当走上第10级台阶只差最后一步时，存在有两种可能：
第1种：从第8级 —> 第10级（一步2个台阶）
第2种：从第9级 —> 第10级（一步1个台阶）

假设：从第0级 —> 第8级，有 x 种走法；

1，1，1，1，1，1，2，2
1，1，1，1，1，2，1，2
1，2，1，1，1，2，2
1，2，1，2，2，2
·······
// 穷举不尽，共 x 种，每种走法的最后一步都是 2(个台阶)

假设：从第0级 —> 第9级，有 y 种走法；

1，1，1，1，1，1，1，2，1
1，1，2，1，1，2，1，1
1，2，1，2，2，1，1
1，2，2，2，2，1
·······
// 穷举不尽，共 y 种，每种走法的最后一步都是 1(个台阶)

那么，从第0级 —> 第10级，共有 x + y 种走法。

故，10级台阶走法 = 9级台阶走法 + 8级台阶走法，即 f(10) = f(9) + f(8);

所以我们需要的函数关系式是 f(n) = f(n - 1) + f(n - 2);

接下来找终止条件：

1级台阶时，走法只有1种（1步1台阶），是 n === 1; 时， return 1;
2级台阶时，走法只有2种（2次1步1台阶或 1步2台阶），是 n === 2; 时， return 2;

由此可以写出递归函数

function fn(n){if(n === 1 || n === 2){return n;}return fun(n - 1) + fun(n - 2);
}

下图展示了函数的执行过程

可见，在函数执行过程中重复调用了多次相同的函数（相同背景色），从而极大消耗了系统的性能。经过测试这个递归函数最多可计算至 f(45);左右的结果（测试需谨慎），这便是递归函数存在的主要问题。

那么如何优化这个问题呢？

即，将递归算法改为循环算法。

通过前面的推导我们知道 f(n) = f(n - 1) + f(n - 2);

1级台阶 ==> 走法：1
2级台阶 ==> 走法：2
3级台阶 ==> 走法：1 + 2 = 3
4级台阶 ==> 走法：2 + 3 = 5
5级台阶 ==> 走法：3 + 5 = 8
6级台阶 ==> 走法：5 + 8 = 13
7级台阶 ==> 走法：8 + 13 = 21
······

即，只要知道前两项（1级台阶和2级台阶）的结果，就可以自底向上依次推算出后面所有项的结果。

于是便可以写出循环函数

function fn(n){if(n === 1 || n === 2){return n;}var left = 1; // 左边的数据var right = 2; // 右边的数据var sum = 0;for(var i = 3 ; i <= n ; i++){ // 循环从第3项开始sum = left + right; // 计算前一次左右数据的和left = right; // 把前一次的right赋值给下一次的leftright = sum; // 把前一次的和赋值给下一次的right}return sum;
}

以上便是通过递归思想将抽象问题逐步简单化，从而得出循环算法的过程。
循环算法解决了递归消耗系统性能的问题，可以计算任意数值。

（当数值太大超出JavaScript数值范围时，返回 Infinity）

总结

1、递归结构简单，易理解，常用于将抽象问题简单化。

2、递归要有终止条件，否则会变成死递归；

3、递归算法运行效率低、性能消耗大，递归深度较大时慎用（等不到结果）；

4、能用递归解决的问题大多都能用循环解决。

【end】

◆

原力计划

◆

《原力计划【第二季】- 学习力挑战》正式开始！即日起至 3月21日，千万流量支持原创作者！更有专属【勋章】等你来挑战

推荐阅读

赔偿谷歌1.8亿美元！前Uber自动驾驶主管被告到破产
“一网打尽”Deepfake等换脸图像，微软提出升级版鉴别技术Face X-Ray
小米回应"暴力裁员"；报告称安卓手机贬值速度是 iPhone 两倍；Ant Design 4.0.1 发布
时间复杂度的表示、分析、计算方法……一文带你看懂时间复杂度！
闪电网络的 5 个优点和4 个缺点、本质、来源与工作原理……一文带你读懂闪电网络！
国内外大厂集结，远程办公大考成绩单发布！

你点的每个“在看”，我都认真当成了AI

https://www.dkcj.cn/info/30628.html

Javascript函数之深入浅出递归思想，附案例与代码！

递归函数的理解

1、生活中的递归

递归函数的使用

实例探索递归函数的书写“套路”

总结

相关文章：

Linux指令--文件和目录属性

Linux内存寻址

iptables 基本命令使用举例

重磅！教育部再次审批179所高校新增本科AI专业

Qt之自定义搜索框

大型网站架构演变和知识体系

Python数据清理终极指南（2020版）

内存地址转换与分段

c++ 普通高精减

腾讯提超强少样本目标检测算法，公开1000类检测训练集FSOD | CVPR 2020

Linux加入到Windows域收藏

哈希函数原理及实现

基于Virtual DOM与Diff DOM的测试代码生成

Win32 环境下的堆栈

在VMWare中配置SQLServer2005集群 Step by Step(四)——集群安装

口罩检测识别率惊人，这个Python项目开源了

CentOS搭建msmtp+mutt实现邮件发送

Linux环境下的堆栈--调试C程序

听说过代码洁癖，Bug洁癖怎么解？

POJO、VO、PO、FormBean区别：

oracle中的sql%rowcount,sql%found、sql%notfound、sql%rowcount和sql%isopen

linux平台的链接与加载

预训练模型ProphetNet：根据未来文本信息进行自然语言生成

模拟进程管理小结，编码规范的重要性

JSPServlet路径问题

Git学习教程（六）Git日志

汇编包含C代码

无需3D运动数据训练，最新人体姿势估计方法达到SOTA | CVPR 2020

Linux内核跟踪之trace框架分析【转】

写给Python开发者：机器学习十大必备技能