递归函数定义
编程语言中,函数Func(Type a,……)直接或间接调用函数本身,则该函数称为递归函数。
要点
- 函数直接或间接调用本身;
- 循环调用结束时机(只有达到了结束时机,才会有最终的结果);
递归的逻辑梳理
- 基本功能函数
- 递推逻辑转化
- 临界条件(基本功能函数调用结束的条件)
示例分析
需求:求出1-100之间,所有整数的和;代码如下:
function sum(n){
if(n===1){
return 1
}else{
return sum(n-1) + n
}
}
console.log(sum(100)); //输出结果5050
基本功能函数
function sum(n){
return sum(n-1) + n;
}
解释:求n+(n-1)的和;
递归逻辑转化
求100的和转化为求99的和;
求99的和转化为求98的和;
求98的和转化为求97的和;
......
求1的和转化为求1的和;(临界条件就是n=1)
常见的递归函数
- Fibonacci数列(斐波那契数列)
function fib(n){
if(n == 0 || n ==1) return 1;
return fib(n-1) + fib(n-2);
}
- 阶乘
function foo(n){
if( n == 1) return 1;
return foo(n - 1) * n;
}
网友评论