1.什么是递归函数:就是在函数体内调用本函数。是一种调用模式,是一种逻辑程序基础的体现(类似于循环)。
当我们知道了什么是递归函数以后接下来的问题就是:
怎么写递归函数:
(1)声明函数(这里的步骤和普通函数的声明一样)。
(2)找使递归函数停止的条件(也是递归函数里最重要的一点)
(3)找关系(此时假设函数的功能已经实现,要找的关系就是找f(n)与f(n-1)的关系)
(4)用f(n-1)去实现f(n)的功能。
下面看一个简单的例子:
利用递归求斐波那契数列(1,1,2,3,5,8,13,21,34,55,89...)
// 第一步:先声明函数fn; // 第二步:找临界关系:通过观察可以发现第一位和第二位的值都为1,所以临界值为n=1或者n=2时直接返回1,函数终止。 // 第二步:观察数列可以发现从第三位的值=第一位+第二位;第四位的值=第二位+第三位...依次类推 // 可以写成如下方式: // 5 = 3 + 2 // 1+2 + 1+1 // 1+1 //第三步:通过上面的拆分发现上面的式子可以表达为: // fn(5) =fn(4) + fn(3) // fn(2)+fn(3) + fn(2)+fn(1) // fn(2)+fn(1) //第四步:通过看上面的式子已经可以很明显的看出fn(n)与fn(n-1)的关系
所以fn(n)=fn(n-1)+fn(n-2),当n为1或者n为2的时候终止 function fn(n){ if(n==1||n==2){ return 1; } else{ return fn(n-1)+fn(n-2); } }
// 此时可以运行查看第四位的值是否正确 console.log(fn(4));
打开控制台可以看到结果:
注意:递归会消耗大量内存,但是它代表了逻辑程序基础的体现。