搜索
首页web前端js教程JavaScript实现递归算法的方法介绍

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

Mar 23, 2019 am 11:42 AM
javascript

本篇文章给大家带来的内容是关于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<= 2这个条件返回1。

  走楼梯问题

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

  代码实现:

  下载 (2).png

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

  最大公约数

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

  代码实现:

  下载 (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视频教程栏目!

以上是JavaScript实现递归算法的方法介绍的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:博客园。如有侵权,请联系admin@php.cn删除
JavaScript的角色:使网络交互和动态JavaScript的角色:使网络交互和动态Apr 24, 2025 am 12:12 AM

JavaScript是现代网站的核心,因为它增强了网页的交互性和动态性。1)它允许在不刷新页面的情况下改变内容,2)通过DOMAPI操作网页,3)支持复杂的交互效果如动画和拖放,4)优化性能和最佳实践提高用户体验。

C和JavaScript:连接解释C和JavaScript:连接解释Apr 23, 2025 am 12:07 AM

C 和JavaScript通过WebAssembly实现互操作性。1)C 代码编译成WebAssembly模块,引入到JavaScript环境中,增强计算能力。2)在游戏开发中,C 处理物理引擎和图形渲染,JavaScript负责游戏逻辑和用户界面。

从网站到应用程序:JavaScript的不同应用从网站到应用程序:JavaScript的不同应用Apr 22, 2025 am 12:02 AM

JavaScript在网站、移动应用、桌面应用和服务器端编程中均有广泛应用。1)在网站开发中,JavaScript与HTML、CSS一起操作DOM,实现动态效果,并支持如jQuery、React等框架。2)通过ReactNative和Ionic,JavaScript用于开发跨平台移动应用。3)Electron框架使JavaScript能构建桌面应用。4)Node.js让JavaScript在服务器端运行,支持高并发请求。

Python vs. JavaScript:比较用例和应用程序Python vs. JavaScript:比较用例和应用程序Apr 21, 2025 am 12:01 AM

Python更适合数据科学和自动化,JavaScript更适合前端和全栈开发。1.Python在数据科学和机器学习中表现出色,使用NumPy、Pandas等库进行数据处理和建模。2.Python在自动化和脚本编写方面简洁高效。3.JavaScript在前端开发中不可或缺,用于构建动态网页和单页面应用。4.JavaScript通过Node.js在后端开发中发挥作用,支持全栈开发。

C/C在JavaScript口译员和编译器中的作用C/C在JavaScript口译员和编译器中的作用Apr 20, 2025 am 12:01 AM

C和C 在JavaScript引擎中扮演了至关重要的角色,主要用于实现解释器和JIT编译器。 1)C 用于解析JavaScript源码并生成抽象语法树。 2)C 负责生成和执行字节码。 3)C 实现JIT编译器,在运行时优化和编译热点代码,显着提高JavaScript的执行效率。

JavaScript在行动中:现实世界中的示例和项目JavaScript在行动中:现实世界中的示例和项目Apr 19, 2025 am 12:13 AM

JavaScript在现实世界中的应用包括前端和后端开发。1)通过构建TODO列表应用展示前端应用,涉及DOM操作和事件处理。2)通过Node.js和Express构建RESTfulAPI展示后端应用。

JavaScript和Web:核心功能和用例JavaScript和Web:核心功能和用例Apr 18, 2025 am 12:19 AM

JavaScript在Web开发中的主要用途包括客户端交互、表单验证和异步通信。1)通过DOM操作实现动态内容更新和用户交互;2)在用户提交数据前进行客户端验证,提高用户体验;3)通过AJAX技术实现与服务器的无刷新通信。

了解JavaScript引擎:实施详细信息了解JavaScript引擎:实施详细信息Apr 17, 2025 am 12:05 AM

理解JavaScript引擎内部工作原理对开发者重要,因为它能帮助编写更高效的代码并理解性能瓶颈和优化策略。1)引擎的工作流程包括解析、编译和执行三个阶段;2)执行过程中,引擎会进行动态优化,如内联缓存和隐藏类;3)最佳实践包括避免全局变量、优化循环、使用const和let,以及避免过度使用闭包。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

mPDF

mPDF

mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )专业的PHP集成开发工具

螳螂BT

螳螂BT

Mantis是一个易于部署的基于Web的缺陷跟踪工具,用于帮助产品缺陷跟踪。它需要PHP、MySQL和一个Web服务器。请查看我们的演示和托管服务。