js 递归函数(js递归调用和算法)

前端这点事 55 0

定义:

1、递归函数就是在函数体内调用本函数;
2、递归函数的使用要注意函数终止条件避免死循环,使用

归的时候必须有一个结束标志,否则会报内存溢出的错误 Maximum call stack size exceeded;

为什么使用递归:

递归是编程算法的一种,通过调用自身,将一些复杂/抽象的问题简单化,便于得出解决方案。

先看一道题:

js 递归函数(js递归调用和算法)-第1张图片-前端这点事


例题:某人需要走上10级台阶,有两种走法,走法A:一步1个台阶;走法B:一步2个台阶。两种走法可以任意交替使用,问走上10级台阶共有多少种方法?
。。。。。。这道题看起来是不是很
头绪,利用递归思想来解决这道问题就简单多了,先看看递归怎么使用。

递归步骤

  1. 写好递归函数

  2. 寻找递推关系

  3. 将递推关系的结构转换为递归体

  4. 将临界条件加入到递归体中

例题1:计算n的阶乘(数学公式:n!=1×2×3×…×(n-1)×n)

  1. 写好递归函数:计算n的阶乘可表达为:fn(n)

  2. 寻找递推关系:根据数学公式:n!=1×2×3×…×(n-1)×n
    (n-1)!为 1×2×3×…×(n-1),可得n!阶乘和(n-1)!的关系为(n-1)!*n

  3. 将递推关系的结构转换为递归体:用函数表示即:fn(n) = fn(n-1)*n,

function fn(n){
	return fn(n-1)*n
}
  1. 将临界条件加入到递归体中(若没有终止条件,函数会继续计算f(0) 、f(-1) 、f(-2) ··· 从而进入死循环,无法得出结果。):

function fn(n){
	if(n===1){
		return 1
	}
	return fn(n-1)*n
}

例题2:斐波那契数列

示例:0 1 1 2 3 5 8 13 21…

  1. 写好递归函数
    第n个值可表达为fn(n)

  2. 寻找递推关系
    根据多年的上课打盹的经验,可以看出21为前两个值8+13的和,13为5+8的值,即:fn(n) = fn(n-1) + fn(n-2)

  3. 将递推关系的结构转换为递归体

function fn(n){	
    return fn(n-1) + fn(n-2)
}
  1. 将临界条件加入到递归体中
    fn(n)临界值为fn(0),若越过的话,会执行f(-1) 、f(-2) ··· 从而进入死循环,无法得出结果(n-1) = 0;(n-2)=0,临界值:1,2;即:f(1) = 0,f(2) = 1

function fn(n){
	if(n<2)return 0
	if(n<3)return 1
	return fn(n-1) + fn(n-2)
}
如果进一步求数列的和,你知道怎么用递归表示了?

如果进一步求数列的和,你知道怎么用递归表示了?

function fn(n){
	if(n<2)return 0
	if(n<3)return 1
	return fn(n-1) + fn(n-2)
}
// sum(n) = sum(n) +第n个的值(fn(n))
function sum(n){
	if(n<2)return 0
	return sum(n-1)+fn(n)
}

现在回过头了分析一下楼梯走法问题:

楼梯走法

某人需要走上10级台阶,有两种走法,走法A:一步1个台阶;走法B:一步2个台阶。两种走法可以任意交替使用,问走上10级台阶共有多少种方法?
我们尝试从递归的角度分析一下
当走上第10级台阶只差最后一步时,存在有两种可能:
第1种:从 第8级 —> 第10级(一步2个台阶)
第2种:从 第9级 —> 第10级(一步1个台阶)
即:10级台阶走法 = 9级台阶走法 + 8级台阶走法
递归关系为:f(10) = f(9)+f(8),f(n) = f(n-1)+f(n-2)
将递推关系的结构转换为递归体:

function fn(n){	
    return fn(n-1) + fn(n-2)
}

1级台阶时,走法只有1种(1步1台阶)
2级台阶时,走法只有2种(1步1台阶或者两步一台阶)
加入临界条件

function fn(n){
	if(n<3)return n
	return fn(n-1) + fn(n-2)
}
思考
fn(10) = fn(9)+fn(8);
fn(9) = fn(8)+fn(7)…以此类推,你会发现发fn(8)重复执行了两次,以f(10)为例子,用图来表示执行过程:

思考

fn(10) = fn(9)+fn(8);
fn(9) = fn(8)+fn(7)…以此类推,你会发现发fn(8)重复执行了两次,以f(10)为例子,用图来表示执行过程:

js 递归函数(js递归调用和算法)-第2张图片-前端这点事

这么看就很直观了(相同颜色表示同一个函数)
由此我们可以发现递归的问题所在了吧,递归存在性能问题。递归层级越庞大,会极大消耗了系统的性能。经过测试楼梯问题那个递归函数最多可计算至 f(45),而且随着n值越大,计算时间越长。
这时候循环算法就用得上了。
根据我们前面的推导
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<3){
        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)。


标签: JavaScript

发表评论 (已有0条评论)

还木有评论哦,快来抢沙发吧~