递归和迭代的对比

大家好，又见面了，我是你们的朋友全栈君。

待到秋来九月八，我花开后百花杀

• 递归
• 迭代
• 特点

递归

程序调用自身的编程技巧称为递归（recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。 递归的主要思考方式在于：把大事化小 递归主要是将长问题变成子问题解决，例如： 求n的阶乘

//An highlighted block 
var foo = 'bar';
int fact(int n){ 
   
  if(n <= 1)
      return 1;
  else
      return n * fact(n - 1);
}

迭代

迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。重复执行一系列运算步骤，从前面的量依次求出后面的量的过程。此过程的每一次结果，都是由对前一次所得结果施行相同的运算步骤得到的。 迭代的主要思考方式是：循环反馈计算 例如： 求n的阶乘

  //An highlighted block 
    var foo = 'bar';
    int fact1(int n)
    { 
   
      int sum = 1;
      int i = 1;
      for(;i <= n;i++){ 
   
        sum *= i;
      }
      return sum;
    }

特点

我们可以发现相比于迭代，递归代码块更加简洁轻便，而迭代冗长。但是如果用于计算量较大的问题呢？ 求第n个斐波那契数。（不考虑溢出） 递归：

  //An highlighted block 
    var foo = 'bar';
    int fib(int n)
    { 
   
      if(n <= 2)
        return 1;
      else
        return fib(n - 1) + fib(n - 2);
    }

fib（50）的计算时间

迭代：

//An highlighted block
 var foo = 'bar';
int fib1(int n)
{ 
   
 int first = 1;
 int second = 1;
 int third = 1;
 while (n > 2) { 
   
  third = first + second;
  first = second;
  second = third;
  n--;
 }
 return third;
}

fib1(50)所用时间

明显可以看到递归所使用的时间复杂度远大于迭代。

为什么递归费时间呢？那么我们再看一下递归在内存中的情况： 我们拿阶乘问题作例子：

在程序递归过程中，每调用一次函数就会创建一个栈帧结构，而在每个栈帧结构中就会创建各自的局部变量，就会占用内存，相比于迭代，在内存方面，递归也占用了更多内存，空间复杂度更高。

综上所述，尽管递归看起来代码简单，但是无论是时间复杂度和空间复杂度来说都是迭代更好，所以在项目中还是推荐使用迭代而不是递归。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/135052.html原文链接：https://javaforall.cn