摘要:递归概念递归是一种针对简单循环难以编程实现的问题,通过函数调用自身,提供优雅解决方案的技术。拥有基础情况或终止条件来停止递归。这个称之为递归调用。为了避免重新创建字符串,使用递归辅助方法来进行改良。
递归概念
递归是一种针对简单循环难以编程实现的问题,通过函数调用自身,提供优雅解决方案的技术。
递归都具有以下三个要点:
使用 if-else 或 switch 语句来引导不同的情况。
拥有基础情况(base case)或终止条件(stopping condition)来停止递归。
每次递归调用都会简化原始问题,让它不断接近基础情况,所以可以用不同的参数调用自身方法,直到它变为这种基础情况。这个称之为递归调用(recursive call)。
示例,计算阶乘
if(n == 0){ // base case return 0; }else { // recursive call return n * factorial(n-1) }递归的优势--斐波那契数列
计算阶乘很容易使用循环改写,某些情况下,用循环不容易解决的问题可以利用递归给出一个直观简单的解法。
斐波那契数列从 0 到 1 开始,之后的每个数都是序列中的前两个数之和,通过递归可以简单的实现出来。
var count = 0; function fib(n) { count++; if(n == 0){ return 0; }else if(n == 1){ return 1; }else { return fib(n-1) + fib(n-2); } } const result = fib(10); console.log("result",result); console.log("count",count); // result 55 // count 177
程序中会出现很多重复调用,求第 10 个斐波那契数,就调用了 177 次自身函数,如果尝试求出更大的斐波那契数,那么相应的调用次数就会急剧的增加。
优化递归调用将计算过的斐波那契值存起来,可以优化递归调用。通过改良,求第 10 个斐波那契数,只调用的 11 次自身函数。而且调用自身函数的次数永远是,n + 1 次,n 代表第 n 个需求的斐波那契数。
var count = 0; const calculated = []; function fib(n) { count++; if(n == 0){ return 0; }else if(n == 1){ return 1; }else { if(!calculated[n-1]){ calculated[n-1] = fib(n-1); } if(!calculated[n-2]){ calculated[n-2] = fib(n-2); } return calculated[n-1] + calculated[n-2]; } } const result = fib(10); console.log("result",result); console.log("count",count); // result 55 // count 11递归辅助方法
有时候可以通过找到一个要解决的初始问题的类似问题,来找到初始问题的解决方案。这个类似的方法称之为递归辅助方法。
举例,如果一个字符串从左读和从右读都是一样的,那么他就是一个回文串(palindrome)。可以通过下面的函数判断。
function palindrome(str) { if(str.length <= 1 ){ return true; }else if(str[0] !== str[str.length - 1]){ return false; }else { return palindrome(str.slice(1,-1)); } } const result = palindrome("ffffdffffd"); console.log(result); // ture
每次调用 palindrome 方法时,都会使用 str.slice 来创建一个新的字符串。
为了避免重新创建字符串,使用递归辅助方法 isPalindrome 来进行改良。
function isPalindrome(str) { return palindrome(str,0,str.length-1); } function palindrome(str,low,high) { if(low >= high){ return true; }else if(str[low] !== str[high]){ return false; }else { low ++; high --; return palindrome(str,low,high); } } const result = isPalindrome("ffffdaaaerffffd"); console.log(result); // false
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/80873.html
摘要:在递归过程中,未完成计算的函数将会挂起压入调用堆栈,不然递归结束的时候没办法进行回溯。这就引出了回溯法回溯法就是在达到递归边界前的某层,由于一些事实导致已经不需要前往任何一个子问题递归,就可以直接返回上一层。 1简介 递归在前端开发中应用还是非常广泛的,首先DOM就是树状结构,而这种结构使用递归去遍历是非常合适的。然后就是对象和数组的深复制很多库也是使用递归实现的例如jquery中的e...
摘要:终止条件递推公式递归的分类通过做大量的题,根据递归解决不同的问题,引申出来的几种解决和思考的方式。我们通过层与层之间的计算关系用递推公式表达出来做计算,经过层层的递归,最终得到结果值。 showImg(https://segmentfault.com/img/remote/1460000019222330); 前言 几个月之前就想写这样一篇文章分享给大家,由于自己有心而力不足,没有把真...
摘要:所以,递归在编程中同样是很重要的一个知识点。举个例子用递归实现求第个斐波那契数。总结起来四个字大事化小继续举斐波那契数的例子三递归是怎样运行的我们通过一道题目来讲解。 ...
摘要:对于函数调用开销,可以利用尾递归来解决,不过目前的引擎并没有实现对尾递归的优化,所以最开始我以为递归没有理由比非递归更快。递归与堆栈非递归的算法使用一个堆栈来实现。 最近刷leetcode 79题 Word Search需要用到DFS算法,由于是刷leetcode,心想不能用递归,影响效率,于是利用stack完成。之后又利用递归(使用cache)实现了一次,结果竟然是递归的算法比非递归...
摘要:简而言之,递归就是自己调用自己,但是这个调用它是有一定条件的,比如子问题须与原始问题为同样的事,且更为简单。当时,这层递归返回,也就是返回到的这层递归。这时,至此,递归结束,返回结果给调用方。 showImg(https://segmentfault.com/img/bVbvZRe?w=1242&h=735); 什么是递归? 维基百科给出了如下定义: 程序调用自身的编程技巧称为递归.递...
阅读 3221·2021-09-09 11:39
阅读 1228·2021-09-09 09:33
阅读 1126·2019-08-30 15:43
阅读 545·2019-08-29 14:08
阅读 1732·2019-08-26 13:49
阅读 2375·2019-08-26 10:09
阅读 1544·2019-08-23 17:13
阅读 2282·2019-08-23 12:57