1.递归和迭代的区别
-
当实体
调用自身时，程序称为递归。 -
当存在
循环（或重复）时，程序称为迭代调用。 -
示例：求一个数的阶乘的程序
时间复杂度比较
-
查找递归的时间复杂度比迭代更难。 -
递归：递归的时间复杂度可以通过根据先前的调用找到第 n 次递归调用的值来找到。因此，根据基本情况找到目标情况，并根据基本情况求解，可以让我们了解递归方程的时间复杂度。 -
迭代：迭代的时间复杂度可以通过找到循环内重复的循环数来找到。
用法比较
-
使用这些技术中的任何一种都是时间复杂度和代码大小之间的权衡。
-
如果时间复杂度是重点，递归调用的次数会很大，那么最好使用迭代。
-
但是，如果时间复杂度不是问题而代码的短小是问题，那么递归将是可行的方法。
-
递归：递归涉及再次调用相同的函数，因此代码长度非常短。然而，正如我们在分析中看到的那样，当递归调用数量相当多时，递归的时间复杂度可能会呈指数级增长。因此，递归的使用在更短的代码中是有利的，但时间复杂度更高。
-
迭代：迭代是代码块的重复。这涉及较大的代码量，但时间复杂度通常低于递归。
开销
-
与迭代相比，递归有大量的开销。
-
递归：递归有函数重复调用的开销，即由于重复调用同一个函数，代码的时间复杂度增加了很多倍。 -
迭代：迭代不涉及任何此类开销。
无限重复
-
递归中的 Infinite Repetition 会导致 CPU crash，但在迭代中，当内存耗尽时它会停止。 -
递归：在Recursion中，由于指定的基本条件错误，可能会出现无限递归调用，在永远不会为假的情况下，不断调用函数，这可能会导致系统CPU崩溃。 -
迭代：由于迭代器赋值或递增错误或终止条件错误而导致的无限迭代将导致无限循环，这可能会或可能不会导致系统错误，但肯定会停止程序的进一步执行。
| 递归 | 迭代 | |
|---|---|---|
| 定义 | 函数调用自身。 | 重复执行的一组指令。 |
| 应用 | 对于功能。 | 对于循环。 |
| 终止 | 通过 base case，这里不会有函数调用。 | 当不再满足迭代器的终止条件时。 |
| 用法 | 当代码大小需要很小并且时间复杂度不是问题时使用。 | 当时间复杂度需要与扩展的代码大小进行平衡时使用 |
| 代码大小 | 更少的代码 | 更多的代码 |
| 时间复杂度 | 非常高（通常是指数）的时间复杂度。 | 时间复杂度相对较低（一般为多项式-对数）。 |
| 空间复杂度 | 空间复杂度高于迭代。 | 空间复杂度较低。 |
| 堆 | 这里的栈是用来存放函数调用时的局部变量的。 | 不使用堆栈。 |
| 速度 | 执行速度很慢，因为它有维护和更新堆栈的开销。 | 通常，它比递归更快，因为它不使用堆栈。 |
| 存储 | 与迭代相比，递归使用更多内存。 | 没有开销，因为迭代中没有函数调用。 |
| 高架 | 拥有重复函数调用的开销。 | 没有开销，因为迭代中没有函数调用。 |
| 无限重复 | 如果递归函数不满足终止条件或未定义或从未达到基本情况，则会导致堆栈溢出错误，并且系统有可能在无限递归中崩溃。 | 如果迭代语句的控制条件永远不为假或控制变量没有达到终止值，就会造成死循环。在无限循环中，它一次又一次地使用 CPU 周期。 |
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
