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

JavaScript 递归 函数 算法

程序员文章站 2022-03-13 17:51:14
在编程的世界里面,递归就是一个自己调用自己的手段,函数内部,调用了自己,循环往复,一种编写函数的特殊写法。...

神秘的递归函数

递归函数,面试官如果询问递归知识,那么面试官的要求较高,

但是公司明文禁止使用递归。

什么是递归函数?

在编程的世界里面,递归就是一个自己调用自己的手段,函数内部,调用了自己,循环往复,一种编写函数的特殊写法。

其实递归函数和循环很类似,递归可以解决循环能做的所有事情,有一些循环不太容易完成的事,递归也可以轻松解决。

下面的代码就是一个简单的递归函数:

function fn(){

     alert("你进入了递归ing~~~");

     fn();
}
fn();

// 在这个函数里面调用了自己,会一直循环往复,没有止境,这种叫做死递归。

递归的三个特点:

  1. 函数自己调用自己
  2. 一般情况有参数
  3. 一般情况下有return

通过一个案例,来了解一下递归~(写一个函数,计算1-n的和?)
首先通过普通的函数写一下。

function sum(n){

     var res = 0;  //声明一个变量记录累加和

     for(var i=0; i<=n; i++){
          res += i;
     };

     return res;  //返回计算结果
}

alert (sum(100));  //5050

// 1-100的累加和

将上面的1-n的和换成递归写法
方法:

  1. 首先去找临界值,即无需计算,直观获得的值
  2. 找这一次和上一次的关系
  3. 假设自身函数已经可以使用,调用自身计算上一次

演变以下写法:

function sum(n){

       // 1 找临界值,当n为1的时候(1的和),结果就是1,所以

        if(n == 1){
            return 1;
        }

       // 2 找这一次和上一次的关系
       //      1至100的和 = 1至99的和 + 100

       // 3 假定sum(n)就是一个求1-n和的函数  
       // 那么: sum(100) = sum(99) + 100   将n替代掉100
       // 即:   sum(n) = sum(n-1) + n  得到

        return sum(n-1) + n;
}

alert (sum(100)); //计算结果同样为5050

分析:

通过内存分析来看一下,内存的管理机制,每一个函数在调用的时候都必须分配空间去执行,直到这个函数被执行完毕以后,再把这段空间给释放掉。

function sum(n){
		//判断 n 的值
        if(n == 1){
            return 1;
        }
        //n不为1时返回值
        return sum(n-1) + n;
}
alert (sum(100)); 

计算机求一个sum(100)的和,也就是说要在当前内存去开辟一个空间计算sum(100)

sum(100)进入函数之后判断 不符合 n==1 的条件,就会返回 sum(99) + 100;

sum(99)的值内存此时并不知道,再次进入函数判断 返回 sum(98) + 99;

sum(98)的值内存此时也不知道,再次进入函数判断 返回 sum(97) + 98;

··············· 依次类推 ···············

sum(3)的值·················进入函数判断 返回 sum(2) + 3;

sum(2)的值内存不知道,再次进入函数判断 返回 sum(1) + 2;

sum(1)进入函数判断 n==1 ,此时返回 1,得到sum(1)的值为1
JavaScript 递归 函数 算法

sum(1)知道了,再往上看 sum(2)返回的是 sum(1) + 2 , 就可以得到sum(2)的值为3

sum(2)知道了,再往上 sum(3)返回的是 sum(2) + 3 ,就可以得到sum(3)的值为6

··············· 依次往上类推 ···············

······················································································得到sum(98)的值;
······················································································再得到sum(99)的值;
······················································································最后得到sum(100)的值。

这是一个不断开辟新的空间,和释放空间的一个过程。每一个要计算的函数都是在开辟空间,直到返回sum(1)的值,然后再用返回值去释放之前的每一段空间,直到算出sum(100)的值,所有占用空间也就释放完毕。

这就是递归,在没算到临界值的时候,会不断的开辟所有的内存去计算每一个函数,最终当临界值算出来以后,才开始依次把之前开辟的内存释放掉。

注意:

在这种计算中,存在一定的风险,我们计算机内存有一定的大小,计算机运行的速度非常快,刚刚计算100的和,内存瞬间开辟100个空间,然后再瞬间释放100个空间,假定数据再大一些的话,比如一个亿,计算机可能承受不了,可能导致蓝屏,或者死机,这也是为什么慎用递归的原因。

结束语

好了,说到这里不知道你对递归有没有了解清楚一点,希望这篇文章对你们有所帮助。
码字不易,点个赞再走呗~~~

本文地址:https://blog.csdn.net/weixin_49293345/article/details/107283473