My Little World

递归

发表于

递归

1.把有一个直接调用自己或通过一系列的调用语句间接的调用用自己的函数，称作递归函数
2.每个递归函数必须有一个终止调用的条件语句，否则陷入永不结束的无穷递归

斐波那契数列

迭代实现

1
2
3
4
5
6
7
8
9
var a=[];
a[0] = 1;
a[1] = 1;
for(var i =2;i<40;i++){
  a[i]=a[i-1]+a[i-2];
}
for(var j=0;j<40;j++){
  console.log(j,a[j]);
}

递归实现

1
2
3
4
5
6
7
8
9
function fib(n){
  if(n<2){
    return 1;
  }
  if(n>1 && n<40){
    return fib(n-1)+fib(n-2);
  }
}
console.log(fib(4));

n!阶乘递归算法

1
2
3
4
5
6
7
8
9
function fib(n){
    if(n>0){
      return n*fib(n-1);
    }else{
      return 1;
    }
    
}
console.log(fib(4));

汉诺塔问题

1
2
3
4
5
6
7
8
9
10
11
function hanoita(n,x,y,z){
  if(n==1){
    console.log(x+"->"+z);
  }else{
    hanoita(n-1,x,z,y);
    console.log(x+"->"+z);
    hanoita(n-1,y,x,z);
  }
}

hanoita(3,"x","y",'z');

递归字符串翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
var string = "hello#";
var count = 0;
function print(){
  if(string[count]!="#"){
    count++;
    print();
  }
  count--;
  if(count>-1 && string[count]!="#"){
    console.log(string[count]);
  }
}
print();

折中查找法递归

代码链接

小结

1.迭代使用循环结构，递归使用选择结构
2.递归能使程序结构更清晰、简洁、容易让人理解，从而减少读懂代码的时间
3.大量的递归会建立函数的副本，会消耗大量时间和内存，而迭代不需要
4.递归函数分为调用和回退阶段，递归的回退顺序是它调用顺序的逆序