递归

发表于

递归

什么是递归

简单说，当函数直接或间接地调用了自己，则发生了递归
递归不一定适用于所有情况，很多情况用迭代比递归更有效，其次，相对来说递归的效率通常要低于迭代得实现，同时，内存占用也会更大。

实现递归的方法

Paul Graham提到一种方法
1.当n是0、1时，结果正确
2.假设函数对于n是正确的，函数对n+1结果也正确

如果两点成立，我们知道这个函数对于所有可能的都是正确的

递归的问题

示例

菲波那切数列

20171129151195276410427.png

1
2
3
4
5
6
7
8
9
10
11
12
13
func main(){
    n,_ := strconv.Atoi(os.Args[1])
    fmt.Println(fib(n))
}
func fib(n int) int {
    if n==0||n==1{
        return 1
    }else{
        return fib(n-1)+fib(n-2)
    }
}

汉诺塔

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
1.每次只能移动一个圆盘.
2.大盘不能叠在小盘上面.

思路: 当N个圆盘在A上，我们已经找到办法将其移动到C杠上，我们怎么移动N+1个圆盘到C杠上呢？很简单，我们首先用将N个圆盘移动到C上的方法将N个圆盘都移动到B上，然后再把第N+1个圆盘(最后一个)移动到C上，再用同样的方法将B杠上的N个圆盘移动到C上，问题解决。

1
2
3
4
5
6
7
8
9
10
11
<?php
function hanoi($n,$a,$b,$c){
    if($n==1){
        echo "move from $a to $b".PHP_EOL;  //当只有一个圆盘,直接从A移动到C上
    }else{
        hanoi($n-1,$a,$b,$c);   //先把n-1个从A移动到B上
        hanoi(1,$a,$c,$b);      //接着把最后一个从A移动到C上
        hanoi($n-1,$b,$c,$a);   //最后从B上移动N-1个圆盘到C上
    }
}

参考

http://blog.csdn.net/vagrxie/article/details/8470798