首页 > 代码库 > 递归与循环的区别

递归与循环的区别

递归与循环是两种不同的解决问题的典型思路。 

递归算法:

优点:代码简洁、清晰,并且容易验证正确性。(如果你真的理解了算法的话,否则你更晕)

缺点:它的运行需要较多次数的函数调用,如果调用层数比较深,需要增加额外的堆栈处理,比如参数传递需要压栈等操作,会对执行效率有一定影响。但是,对于某些问题,如果不使用递归,那将是极端难看的代码。

循环算法:

优点:速度快,结构简单。

缺点:并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话,最好使用循环。

递归算法 和循环算法总结
1. 一般递归调用可以处理的算法,也通过循环去解决常需要额外的低效处理 。
2. 现在的编译器在优化后,对于多次调用的函数处理会有非常好的效率优化,效率未必低于循环。

以下是Java代码实现(递归与递推两种方式):

[java]  import java.util.Scanner; 
 
/**
 * Fibonacci
 *
 * @author tongqian.zhang
 */ 
public class Fibonacci { 
 
    public static void main(String[] args) { 
        Scanner scanner = new Scanner(System.in); 
        System.out.println("Please input this fibonacci n:"); 
        int n = scanner.nextInt(); // 假设输入为大于零的整数  
         
        System.out.println(fibonacci(6) + ":" + fibonacciNormal(6)); 
         
        int sum = 0; 
        for(int i = 1; i <= n; i++){ 
            sum += fibonacci(i); 
        } 
        System.out.println(sum); 
    } 
     
    // 递归实现方式  
    public static int fibonacci(int n){ 
        if(n <= 2){ 
            return 1; 
        }else{ 
            return fibonacci(n-1) + fibonacci(n-2); 
        } 
    } 
     
    // 递推实现方式  
    public static int fibonacciNormal(int n){ 
        if(n <= 2){ 
            return 1; 
        } 
        int n1 = 1, n2 = 1, sn = 0; 
        for(int i = 0; i < n - 2; i ++){ 
            sn = n1 + n2; 
            n1 = n2; 
            n2 = sn; 
        } 
        return sn; 
    }