JavaScript实现递归算法的方法介绍

千雪小哥_1653

千雪小哥_1653

2019-03-23

4380人浏览

转载

本篇文章给大家带来的内容是关于javascript实现递归算法的方法介绍,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

我们先来看一下定义。递归算法,是将问题转化为规模缩小的同类问题的子问题,每一个子问题都用一个同样的算法去解决。一般来说,一个递归算法就是函数调用自身去解决它的子问题。

  递归算法的特点:

  1. 在函数过程中调用自身。
  2. 在递归过程中,必须有一个明确的条件判断递归的结束,既递归出口。
  3. 递归算法简洁但效率低,通常不作为推荐算法。

  上面这些是百度百科的解释,讲的也是十分明确,大家配合实例来细细琢磨。

  阶乘

  问题描述: n! = n*(n-1)*...2*1

  代码实现:

下载.png

  我们拿到问题的时候,我们按照定义的说明,可以先将规模缩小到同类的子问题。比如,n! 是等于 n* (n-1)!,然后(n-1)! = (n-1)*(n-2)!。这样依次往下推,直到if的出口。这里用了arguments.callee,是为了防止函数名的紧密耦合,在这里它等同于factorial(n-1)。函数实现起来是不是简洁明了呢。当然因为问题规模简单,其实用循环也是可以实现的,大家可以尝试一下。

斐波那契数列

  问题描述:1, 1, 2, 3, 5, 8, 13, 21, 34, ....... 求第n个数是多少。

  代码实现:

  下载 (1).png

  其实用刚才的想法实现,也是非常的简单的。通过分析可以得到第n个数,是前两个数的和,通过这个我们就可以通过递归,不断获得所需要的前两个数,直到n

  走楼梯问题

  问题描述:楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶或者3阶,计算共有多少种不同的走法。

  代码实现:

  下载 (2).png

  这其实就是一个斐波那契数列的一种实现。我们分析的时候,可以转化成小规模的子类问题。当到达指定阶梯的最后一步的时候,可以有三种种情况,一是上一步,二是上两步,三是上三步。所以总的方法是F(n) = F(n-1) + F(n-2) + F(n-3)。然后自然就成了各自的小计算,不断循环下去,直到判断条件的发生。

  最大公约数

  问题描述:给两个数,如果两个数相等,最大公约数是其本身。如果不等,取两个数相减的绝对值和两个数中最小的数比较,相等则为最大公约,不等则继续上面的算法,直到相等。

JavaScript规范工具(免费版)
JavaScript规范工具(免费版)

面向个人开发者的JavaScript代码风格指南,涵盖核心规则与基础代码审查能力。

下载

  代码实现:

  下载 (3).png

  没什么好说的,照问题描述所要求的实现就可以了。递归的出口便在于a等于b。

 汉诺塔

  问题描述:大家都或多或少的玩过,这里就不再赘述了。

  代码实现:

  下载 (4).png

  在我没有体会到递归的精粹前,我对这个问题简直百思不得其解。我一直问自己,我怎么知道下一个该去哪里?后来,我就知道,我其实更关心的是,最后那一个该怎么走。这个怎么说呢?我们可以从头想起,我们如果只有1个盘,我们可以让它到C柱,也可以到B柱。自然两个盘,也可以实现。3个盘,也是可以的吧。那我们就讲4个盘的情况。4个盘要完成就要将A上的圆盘,完全转移到C上。我们把前3个盘当作一个整体放到B上,然后第4个盘就可以到C上了,然后我们再将前三个放到C上,就成功了。那前三个盘,又可以重新当作一个新游戏,让前两个盘,当一个整体,依次类推。这样我们只需要关心大的整体的事,其它的就转成小规模问题解决就好了。

     二分法快排

  问题描述:使用二分法,对一个数组进行由小到大的排序。

  代码实现:

  下载 (5).png

嗯...第二次写这东西啦。这一次对递归的实现也是比上次清晰很多了。其实也是将大规模化为小规模,关心一个大整体,让其不断化为小规模进行计算。具体可以去原来那篇随笔进行查看。

DOM树的递归

问题描述:获取一个节点的所有父节点的tagName

代码实现:

  下载 (6).png

大概都能看懂就不说什么啦。相比之前的汉诺塔和快排什么的,这个还是挺简单的了,但是最接近我们JavaScript的实际应用。

本篇文章到这里就已经全部结束了,更多其他精彩内容可以关注PHP中文网的JavaScript视频教程栏目!

Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南

相关文章

java速学教程(入门到精通)
java速学教程(入门到精通)

java怎么学习?java怎么入门?java在哪学?java怎么学才快?不用担心,这里为大家提供了java速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

javascript

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
python如何计算数的阶乘
python如何计算数的阶乘

方法:1、使用循环;2、使用递归;3、使用math模块;4、使用reduce函数。更多详细python如何计算数的阶乘的内容,可以阅读下面的文章。

2023.11.13

565

5

python求阶乘教程大全
python求阶乘教程大全

本专题整合了python求阶乘相关教程,阅读专题下面的文章了解更多详细内容。

2025.11.08

280

12

python语言求阶乘
python语言求阶乘

本专题整合了python中阶乘相关教程,阅读专题下面的文章了解更多详细步骤。

2025.12.06

427

15

DOM是什么意思
DOM是什么意思

dom的英文全称是documentobjectmodel,表示文件对象模型,是w3c组织推荐的处理可扩展置标语言的标准编程接口;dom是html文档的内存中对象表示,它提供了使用javascript与网页交互的方式。想了解更多的相关内容,可以阅读本专题下面的文章。

2024.08.14

6561

7

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7436

4

Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

2026.11.20

0

7

Navicat入门教程大全
Navicat入门教程大全

本专题整理Navicat入门教程,从认识软件界面到开展数据库操作,介绍初次使用需要了解的知识和方法。内容兼顾连接配置、数据管理及日常使用中的疑问,方便用户按学习进度查阅,为后续实践和独立操作打好基础。

2026.11.20

0

17

Navicat数据库连接配置指南
Navicat数据库连接配置指南

从确认数据库信息到建立可用连接,本专题串联Navicat连接数据库的相关知识和操作方法。既有初次配置时需要了解的基础内容,也有连接后的检查思路,方便用户按实际需求查阅教程,逐步熟悉数据库连接的设置流程。

2026.11.20

0

10

PHP8.6数组与数据处理教程
PHP8.6数组与数据处理教程

本专题汇总PHP8.6数组与数据处理教程,涵盖CSV读取和导出、引用遍历删除、array_filter回调模式、配置键名冲突、pathinfo文件名校验、GMP大整数进制转换及UTF-8正则筛选,说明升级兼容变化、输入范围和失败处理方法。

2026.11.20

0

8

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
WebStorm 官方调试文档
WebStorm 官方调试文档

共0课时 | 0人学习

React 教程
React 教程

共58课时 | 12.6万人学习

TypeScript 教程
TypeScript 教程

共19课时 | 6.9万人学习