递归和迭代区别详细介绍

桃扇骨 2023-09-25 21:58 30阅读 0赞

# 1.递归和迭代的区别 #

*  当实体`调用自身`时，程序称为`递归`。
 *  当存在`循环（或重复）`时，程序称为`迭代调用`。
 *  示例：求一个数的阶乘的程序

> 时间复杂度比较

*  `查找递归的时间复杂度比迭代更难。`
 *  `递归`：递归的时间复杂度可以通过根据先前的调用找到第 n 次递归调用的值来找到。因此，根据基本情况找到目标情况，并根据基本情况求解，可以让我们了解递归方程的时间复杂度。
 *  `迭代`：迭代的时间复杂度可以通过找到循环内重复的循环数来找到。

> 用法比较

*  使用这些技术中的任何一种都是时间复杂度和代码大小之间的权衡。
 *  如果时间复杂度是重点，递归调用的次数会很大，那么最好使用迭代。
 *  但是，如果时间复杂度不是问题而代码的短小是问题，那么递归将是可行的方法。
 *  `递归`：`递归涉及再次调用相同的函数`，因此代码长度非常短。然而，正如我们在分析中看到的那样，`当递归调用数量相当多时，递归的时间复杂度可能会呈指数级增长。`因此，递归的使用在`更短的代码中是有利的，但时间复杂度更高`。
 *  `迭代`：迭代是`代码块的重复`。这涉及`较大的代码量`，但`时间复杂度通常低于递归`。

> 开销

*  与迭代相比，递归有大量的开销。
 *  `递归`：递归有函数重复调用的开销，即由于`重复调用同一个函数`，`代码的时间复杂度增加了很多倍`。
 *  `迭代`：迭代不涉及任何此类开销。

> 无限重复

*  `递归`中的 Infinite Repetition 会导致 CPU crash，但在迭代中，当内存耗尽时它会停止。
 *  `递归`：在Recursion中，由于指定的基本条件错误，可能会出现`无限递归调用`，在永远不会为假的情况下，不断调用函数，这可能会`导致系统CPU崩溃`。
 *  `迭代`：由于迭代器赋值或递增错误或终止条件错误而导致的无限迭代将`导致无限循环`，这可能会或可能不会导致系统错误，但肯定会停止程序的进一步执行。

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>递归</th> 
   <th>迭代</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>定义</td> 
   <td>函数调用自身。</td> 
   <td>重复执行的一组指令。</td> 
  </tr> 
  <tr> 
   <td>应用</td> 
   <td>对于功能。</td> 
   <td>对于循环。</td> 
  </tr> 
  <tr> 
   <td>终止</td> 
   <td>通过 base case，这里不会有函数调用。</td> 
   <td>当不再满足迭代器的终止条件时。</td> 
  </tr> 
  <tr> 
   <td>用法</td> 
   <td>当代码大小需要很小并且时间复杂度不是问题时使用。</td> 
   <td>当时间复杂度需要与扩展的代码大小进行平衡时使用</td> 
  </tr> 
  <tr> 
   <td>代码大小</td> 
   <td>更少的代码</td> 
   <td>更多的代码</td> 
  </tr> 
  <tr> 
   <td>时间复杂度</td> 
   <td>非常高（通常是指数）的时间复杂度。</td> 
   <td>时间复杂度相对较低（一般为多项式-对数）。</td> 
  </tr> 
  <tr> 
   <td>空间复杂度</td> 
   <td>空间复杂度高于迭代。</td> 
   <td>空间复杂度较低。</td> 
  </tr> 
  <tr> 
   <td>堆</td> 
   <td>这里的栈是用来存放函数调用时的局部变量的。</td> 
   <td>不使用堆栈。</td> 
  </tr> 
  <tr> 
   <td>速度</td> 
   <td>执行速度很慢，因为它有维护和更新堆栈的开销。</td> 
   <td>通常，它比递归更快，因为它不使用堆栈。</td> 
  </tr> 
  <tr> 
   <td>存储</td> 
   <td>与迭代相比，递归使用更多内存。</td> 
   <td>没有开销，因为迭代中没有函数调用。</td> 
  </tr> 
  <tr> 
   <td>高架</td> 
   <td>拥有重复函数调用的开销。</td> 
   <td>没有开销，因为迭代中没有函数调用。</td> 
  </tr> 
  <tr> 
   <td>无限重复</td> 
   <td>如果递归函数不满足终止条件或未定义或从未达到基本情况，则会导致堆栈溢出错误，并且系统有可能在无限递归中崩溃。</td> 
   <td>如果迭代语句的控制条件永远不为假或控制变量没有达到终止值，就会造成死循环。在无限循环中，它一次又一次地使用 CPU 周期。</td> 
  </tr> 
 </tbody> 
</table>

# 2.代码 #

public class Test {
        
        // ----- 递归 -----
        // 求给定数的阶乘的方法
        static int factorialUsingRecursion(int n)
        {
        
            if (n == 0)
                return 1;
    
            // 递归呼叫
            return n * factorialUsingRecursion(n - 1);
        }
    
        // -----迭代 -----
        //求给定数的阶乘的方法
        static int factorialUsingIteration(int n)
        {
        
            int res = 1, i;
    
            // 迭代
            for (i = 2; i <= n; i++)
                res *= i;
    
            return res;
        }
    
        public static void main(String[] args)
        {
        
            int num = 5;
            System.out.println("Factorial of " + num
                    + " using Recursion is: "
                    + factorialUsingRecursion(5));
    
            System.out.println("Factorial of " + num
                    + " using Iteration is: "
                    + factorialUsingIteration(5));
        }
    }

Factorial of 5 using Recursion is: 120
    Factorial of 5 using Iteration is: 120