递归

alphahans 发布于2019-08-20 12:14 / 1057人阅读

摘要：递归概念递归是一种针对简单循环难以编程实现的问题，通过函数调用自身，提供优雅解决方案的技术。拥有基础情况或终止条件来停止递归。这个称之为递归调用。为了避免重新创建字符串，使用递归辅助方法来进行改良。

递归概念

递归是一种针对简单循环难以编程实现的问题，通过函数调用自身，提供优雅解决方案的技术。

递归都具有以下三个要点：

使用 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

GPU云服务器云服务器树形递归递归编程递归打印递归访问

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/80873.html

js算法入门（3）--递归

摘要：在递归过程中，未完成计算的函数将会挂起压入调用堆栈，不然递归结束的时候没办法进行回溯。这就引出了回溯法回溯法就是在达到递归边界前的某层，由于一些事实导致已经不需要前往任何一个子问题递归，就可以直接返回上一层。 1简介递归在前端开发中应用还是非常广泛的，首先DOM就是树状结构，而这种结构使用递归去遍历是非常合适的。然后就是对象和数组的深复制很多库也是使用递归实现的例如jquery中的e...

jzman 2019-08-22 16:31 评论0 收藏0
数据结构与算法之精讲「递归系列」

摘要：终止条件递推公式递归的分类通过做大量的题，根据递归解决不同的问题，引申出来的几种解决和思考的方式。我们通过层与层之间的计算关系用递推公式表达出来做计算，经过层层的递归，最终得到结果值。 showImg(https://segmentfault.com/img/remote/1460000019222330); 前言几个月之前就想写这样一篇文章分享给大家，由于自己有心而力不足，没有把真...

zhichangterry 2019-08-26 13:50 评论0 收藏0
【C语言】玩转递归——学好递归，你需要掌握的知识！

摘要：所以，递归在编程中同样是很重要的一个知识点。举个例子用递归实现求第个斐波那契数。总结起来四个字大事化小继续举斐波那契数的例子三递归是怎样运行的我们通过一道题目来讲解。 ...

Donne 2021-09-09 09:33 评论0 收藏0
对于递归的傲慢与偏见

摘要：对于函数调用开销，可以利用尾递归来解决，不过目前的引擎并没有实现对尾递归的优化，所以最开始我以为递归没有理由比非递归更快。递归与堆栈非递归的算法使用一个堆栈来实现。最近刷leetcode 79题 Word Search需要用到DFS算法，由于是刷leetcode，心想不能用递归，影响效率，于是利用stack完成。之后又利用递归（使用cache）实现了一次，结果竟然是递归的算法比非递归...

Labradors 2019-08-23 12:58 评论0 收藏0
递归，就是这么简单

摘要：简而言之，递归就是自己调用自己，但是这个调用它是有一定条件的，比如子问题须与原始问题为同样的事，且更为简单。当时，这层递归返回，也就是返回到的这层递归。这时，至此，递归结束，返回结果给调用方。 showImg(https://segmentfault.com/img/bVbvZRe?w=1242&h=735); 什么是递归？维基百科给出了如下定义：程序调用自身的编程技巧称为递归.递...

woshicixide 2019-08-19 10:21 评论0 收藏0
递归函数的执行

摘要：递归一个函数可以指向并调用自身。这是的一个独特的用法，在这个结构下无法替代，出错但我们可以用下面这种方式，把递归函数赋值给一个变量递归(Recursion) 一个函数可以指向并调用自身(call itself)。有三种方法可以达到这个目的：函数名 arguments.callee 作用域下的一个指向该函数的变量名上述概念引用自MDN，对递归概念不清楚的可以自行查看；递归函数...

tomato 2019-08-21 11:37 评论0 收藏0