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

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

 一.递归函数的理解

1、生活中的递归

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

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

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

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

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

  • 调用自身

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

  1. 终止条件
  2. 逐步靠近终止条件

案例中的终止条件是:当 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级台阶共有多少种方法?

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

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

当走上第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); 
} 

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

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

可见,在函数执行过程中重复调用了多次相同的函数(相同背景色),从而极大消耗了系统的性能。经过测试这个 递归函数 最多可计算至 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赋值给下一次的left 
        right = sum; // 把前一次的和赋值给下一次的right 
    } 
    return sum; 
} 

以上便是通过递归思想将抽象问题逐步简单化,从而得出循环算法的过程。

循环算法 解决了 递归 消耗系统性能的问题,可以计算任意数值。

(当数值太大超出JavaScript数值范围时,返回 Infinity)

四.总结

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

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

相关推荐