欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JavaScript递归函数详解:如何使用递归及简单的递归案例

程序员文章站 2022-04-19 13:36:53
一、什么是递归函数?递归是一种在程序设计语言里面被广泛使用的算法,通过直接或间接来调用自身,将大型的复杂问题层层转化为一个与原问题相似但规模较小的问题来求解,这就是递归。而在JavaScript中,函数直接或间接的调用自己,则该函数便称为递归函数。二、如何正确的使用递归函数?一般来说,递归函数是需要有边界条件的,如果没有边界条件,那么函数就会无限制的调用本身,从而出现函数死循环,就比如下面这个例子。function fn(){//定义函数fnconsole.log(1);//在控制...

一、什么是递归函数?

递归是一种在程序设计语言里面被广泛使用的算法,通过直接或间接来调用自身,将大型的复杂问题层层转化为一个与原问题相似但规模较小
的问题来求解,这就是递归。而在JavaScript中,函数直接或间接的调用自己,则该函数便称为递归函数。

二、如何正确的使用递归函数?

一般来说,递归函数是需要有边界条件的,如果没有边界条件,那么函数就会无限制的调用本身,从而出现函数死循环,就比如下面这个例子。

function fn(){			//定义函数fn
	console.log(1);		//在控制台打印输出1
	fn();				//调用函数本身
}
fn();					//调用函数

上述代码是一个典型的死递归,当在外部调用函数fn时,会先打印数字1,然后再次调用函数,再打印1…最终陷入永无止境的循环之中,如果电脑配置不好的,甚至可能导致死机。所以为了避免这种现象出现,我们应该知道如何正确的使用递归函数。

正确使用递归函数需要满足两个条件

  1. 在每一次调用自己时,必须是(在某种意义上)更接近于解;

    简单来说,就是函数在不断重复的做同一件事情,而每做完一次循环,距离最终所需要的答案就会越来越近。

  2. 必须有一个终止处理或计算的出口。

    这句话还是很好理解的,为了避免死递归的出现,我们需要设置一个结束条件,但条件满足时,那么就会结束函数。

三、简单的JavaScript递归函数案例

1. 实现1至5的和

首先我们进行分析:
1至5的和,就是1+2+3+4+5,而如果利用递归的想法来做的话,我们可以每次只实现一次和的计算。

  • 先算 1 + 2 得 3
  • 再算 3 + 3 得 6
  • 再算 6 + 4 得 10
  • 再算 10 + 5 得 15
  • 结束

下面就要让我们利用JS代码进行实现:

  • 开始书写,写递归函数先要写结束条件(为了避免出现 “死递归”)。
function add(n) {
  // 传递进来的是 5
  // 当 n === 1 的时候要结束
  if (n === 1) {
    return 1}
}
add(5)
  • 再写不满足条件的时候我们的递归处理:
function add(n) {
  // 传递进来的是 5
  // 当 n === 1 的时候要结束
  if (n === 1) {
    return 1
  } else {
    // 不满足条件的时候,就是当前数字 + 比自己小 1 的数字
    return n + add(n - 1) ;
  }
}
add(5)

最终返回的值便是1至5的和,而在这个递归函数里面,n是一个形参,我们可以输入任何数字来进行计算,也就是完成1至n的和计算。并且如果我们简单的修改一下代码,计算阶乘也是十分轻松的。

2. 计算斐波那契数列的第N项

斐波那契数列(Fibonacci sequence),又称黄金分割数列。因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上, 斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3)。

  • 书写递归函数代码第一步:依然是先写结束条件。
 function fibonacci(n){
            if(n==1){
                return 1;
            }
            if(n==2){
                return 1;
            }
        }
fibonacci(n)
  • 再写不满足条件的时候我们的递归处理:
 function fibonacci(n){
            if(n==1){
                return 1;
            }
            if(n==2){
                return 1;
            }
            //n = 3 :return fibonacci(2)+fibonacci(1)
            //n = 4 :return fibonacci(3)+fibonacci(2)
            return fibonacci(n-1)+fibonacci(n-2);
        }
 fibonacci(6)

四、总结递归函数的优缺点

优点:结构清晰, 可读性强, 而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、 调试程序带来很大方便。

缺点:递归算法的运行效率较低, 无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

使用建议:在使用递归时,要注意对递归函数的参数类型的检查,一定要保证有一个终止处理或计算的出口。否则很容易演变为死循环,从而造成内存溢出。

本文地址:https://blog.csdn.net/weixin_43132385/article/details/107280286