数据结构之递归调用

什么是递归

即重复循环，想想《盗梦空间》《开端》你就很有感觉了 但是循环不能一直让他循环下去，都会有一个结束标志，比如盗梦空间里的陀螺，当他能够正常停下，代表回到了真实世界，开端， 阻止了锅姨引爆炸弹，拯救全车人，即退出循环,这些都是结束标志

//递归实现 n是下标
class Factorial {
    static int factorial( long n ) {
        if (n <= 1) return n ; // 终止条件 ( 阻止锅姨 ！！！) 
        return factorial(n-1)+factorial(n-2); // 递归调用 (循环中)
    }
}

//循环实现
public static int fun(int n){
       if(n<=1) return n;
       int first=0;
       int second=1;
       for(int i=0;i<n-1;i++){
       int sum=first+second;
       first=second;
       second=sum;
    }
}

递归算法：优点：代码简洁、清晰，并且容易验证正确性。
缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。但是，对于某些问题，如果不使用递归，那将是极其难看的代码。
循环算法：优点：速度快，结构简单。
缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。
递归算法和循环算法总结：
1.一般递归调用可以处理的算法，也通过循环去解决常需要额外的低效处理。
2.现在的编译器在优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。
3.递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换，而不影响程序的阅读，那么替换成递归往往是好的