从快速排序的角度来看，迭代和递归之间的区别

在上述快速排序中递归和迭代的区别，使用了两种方法，即迭代和递归. 其中，QuickSort函数是递归，而Partition是迭代. 让我们看一下递归和迭代之间的异同:

1. 对于迭代和递归，都使用循环结构. 迭代是循环的显式使用. 上面的Partition函数是while循环的显式使用，而递归是重复函数的调用本身（可以是间接的）（也可以是直接的）来实现循环，QuickSort函数是直接调用自身来实现循环.

2. 他们也有不同的方式来结束循环. 对于迭代，当不满足循环条件时，迭代结束. 在分区函数中，当i> = j时，迭代结束；否则，迭代结束. 对于递归，则当不满足基本条件或满足结束条件时，递归结束. 对于QuickSort函数，当front> = end时，递归结束.

3. 实际上，对于迭代而言，解决问题的方法是不断修改迭代变量的值，直到遇到导致循环失败的迭代变量为止. 递归是继续产生原始问题的简化副本，直到问题对基本情况而言是简单的.

4. 递归使用重复调用函数的机制，并不断为程序使用堆栈空间来存储函数数据，这使算法的时间和空间变得复杂. 迭代是在循环体内执行的，这避免了使用由递归引起的问题. 从理论上讲，可以使用递归来解决可以使用递归解决的问题. 但是之所以我们仍然使用递归，使用递归可以更好地反映问题，并使程序更易于理解和调试. 使用迭代时，程序逻辑不是很直观.

很容易理解前三点. 第四点，我们将通过该程序进行解释:

QuickSort完成的工作是在前端不少于结束时始终调用自身以推栈，以了解程序的操作，并且每次推栈时递归和迭代的区别，CPU需要处理以下信息: 函数并将这些信息写入程序堆栈，但是从堆栈到堆栈的开销不是很高，但是使用递归，有时所需的循环数非常大，这会带来很多开销.

但是递归编写的算法非常清晰，但是花一点时间来了解使用迭代的程序的逻辑结构. 让我们纠正程序错误:

第一个是递归函数QuickSort的问题. 从直觉上可以看出，它还对迭代过程中反复确定的元素进行排序. 这不是必需的，因此递归过程中调用的部分应为加或减.

让我们再次看一下迭代函数Partition的问题. 我首先看了很久这个功能，却没有发现问题. 经过更系统的分析后，我研究了问题并将功能分为三个状态. : 开始，中间和结束.

开始时，选择的中间值i和j是合理的. 排除

在中间，比较符号没有问题. 我注意到，当i> j时，i和j可能会出现在while循环中.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-259958-1.html