递归程序和迭代程序是可以互相转化的！ 将递归程序转化为迭代程序的方式是使用栈，这是栈常见的一个用处。因为计算机实现递归的本质就是用栈。
一、第一种方法：尾迭代
尾迭代：如果一个递归函数在函数体中只有一个地方调用自身且这个地方位于return处。
尾迭代转化为递归的模式为： T tailRecursiveFoo(U x, V y) { if (bar(x, y)) return baz(x,y); else { ⋮ // block 1 return tailRecursiveFoo(w, z); } }
To:
T Foo(U x, V y) { while (! bar(x, y)) { ⋮ // block 1 x = w; y = z; } return baz(x,y); }
例子1： // recursive int fac1(int n) { if (n <= 0) return 1; return n * fac1(n-1); } // iterative int fac2(int n) { int i = 1, y = 1; for (; i <= n; ++i) y *= i; return y; }
例子2： unsigned int binarySearch (T v[], unsigned int n, const T& value) // search for value in ordered array of data // return index of value, or index of // next smaller value if not in collection { binarySearch (v, 0, n, value); }
unsigned int binarySearch (T v[], unsigned int low, int high, const T& value) { // repeatedly reduce the area of search // until it is just one value if (low < high) { int mid = (low + high) / 2; if (v[mid] < value) { return binarySearch (v, mid + 1, high, value); } else { return binarySearch (v, low, mid, value); } } else // return the lower value return low; }
becomes unsigned int binarySearch (T v[], unsigned int n, const T& value) // search for value in ordered array of data // return index of value, or index of // next smaller value if not in collection {
int low = 0; int high = n;
// repeatedly reduce the area of search // until it is just one value while (low < high) { int mid = (low + high) / 2; if (v[mid] < value) { low = mid + 1; } else { high = mid; } } // return the lower value return low; }
二、第二种方法：使用栈 cpu依靠将函数执行现场保存到栈中，来执行递归程序。我们可以利用显示的栈来模拟这个过程，从而将递归程序转化为迭代程序。
模板：
T recursiveFoo (U param1, V param2)
{
U local1;
V local2;
⋮ // code block 1
recursiveFoo (local1, local2);
⋮ // code block 2
recursiveFoo (param1, local2);
⋮ // code block 3
recursiveFoo (local1, param2);
⋮ // code block 4
}
becomes
T iterativeFoo (U param1, V param2){
U local1;
V local2;
FooStack stk;
stk.push ({param1, param2, local1, local2, 1});
while (!stk.empty())
{
// get parameters from stack
FooStackInfo stkTop = stk.top();
param1 = stkTop.param1;
param2 = stkTop.param2;
local1 = stkTop.local1;
local2 = stkTop.local2;
stk.pop();
switch (stkTop.location) {
case 1:
⋮ // code block 1
stk.push ({param1, param2, local1, local2, 2});
stk.push ({local1, local2, local1, local2, 1});
break;
case 2:
⋮ // code block 2
stk.push ({param1, param2, local1, local2, 3});
stk.push ({param1, local2, local1, local2, 1});
break;
case 3:
⋮ // code block 3
stk.push ({param1, param2, local1, local2, 4});
stk.push ({local1, param2, local1, local2, 1});
break;
case 4:
⋮ // code block 4
break;
}
} }
特例是：如果递归函数都在一起，且在程序的末尾，则无需存储代码的位置信息，无需switch case，只需要简单的push一次。
先给出这个特例的一个应用，我要将一个快速排序的递归实现改成迭代实现。附测试结果和代码如下： 控制台输出： 迭代快速排序： -1 1 2 3 4 5 8 9 9 12
public class Main { public static void main(String[] args) { int [] arrray = new int[]{8,3,4,12,5,1,2,9,9, -1}; System.out.println("迭代快速排序：");
QuickSortUtil.iterationQuickSort(arrray);
for (int a : arrray){
System.out.print(a);
System.out.print(" "); } } }
class Pair<T1, T2>{
private T1 first;
private T2 second;
public Pair(T1 t1, T2 t2) {
this.first = t1;
this.second = t2;
}
public T1 getFirst() {
return first;
}
public void setFirst(T1 first) {
this.first = first;
}
public T2 getSecond() {
return second;
}
public void setSecond(T2 second) {
this.second = second;
} }
class QuickSortUtil{
static public void quickSort(int[] array){
quickSort(array, 0, array.length - 1);
}
static public void iterationQuickSort(int[] array){
iterationQuickSort(array, 0, array.length - 1);
}
static private void quickSort(int[] array, int begin, int end){
if (begin < end){
int stardardIndex = quickSortUnit(array, begin, end);
quickSort(array, begin, stardardIndex - 1);
quickSort(array, stardardIndex + 1, end);
}
}
static private void iterationQuickSort(int[] array, int begin, int end){
Stack<Pair<Integer, Integer>> stack = new Stack();
stack.push(new Pair<Integer, Integer>(begin, end));
while (!stack.isEmpty()){
begin = stack.peek().getFirst();
end = stack.peek().getSecond();
stack.pop();
if (begin < end) {
int stardardIndex = quickSortUnit(array, begin, end);
stack.push(new Pair<Integer, Integer>(begin, stardardIndex - 1));
stack.push(new Pair<Integer, Integer>(stardardIndex + 1, end));
}
}
}
static private int quickSortUnit(int[] array, int begin, int end){
int standard = array[begin];
int l = begin; int h = end;
while (l < h) {
while (array[h] > standard && l < h) {
--h;
}
if (l < h) {
array[l++] = array[h];
}
while (array[l] < standard && l < h) {
++l;
}
if (l < h) {
array[h--] = array[l];
}
}
if (l == h){
array[l] = standard;
}
return l;
} }
接下来考虑通过的模式，就是需要记录代码位置的模式的一个应用： 我要将递归实现的归并排序算法改成一个用迭代去实现，测试结果和代码如下：
迭代归并排序： -1 1 2 3 4 5 8 9 9 12
public class Main {
public static void main(String[] args) { int [] arrray1 = new int[]{8,3,4,12,5,1,2,9,9, -1}; System.out.println("迭代归并排序：");
MergeSortUtil.mergeSort(arrray1);
for (int a : arrray1){
System.out.print(a);
System.out.print(" ");
}
}
}
class Three<T1, T2, T3>{
private T1 first;
private T2 second;
private T3 third;
private int location;
public Three(T1 first, T2 second, T3 third, int location) {
this.first = first;
this.second = second;
this.third = third;
this.location = location;
}
public int getLocation() {
return location;
}
public void setLocation(int location) {
this.location = location;
}
public T1 getFirst() {
return first;
}
public void setFirst(T1 first) {
this.first = first;
}
public T3 getThird() {
return third;
}
public void setThird(T3 third) {
this.third = third;
}
public T2 getSecond() {
return second;
}
public void setSecond(T2 second) {
this.second = second;
} }
class MergeSortUtil{
public static void mergeSort(int[] array){
mergeSort(array, 0, array.length / 2, array.length - 1);
}
public static void iterationMergeSort(int[] array){
iterationMergeSort(array, 0, array.length / 2, array.length - 1);
}
private static void iterationMergeSort(int[] array, int begin1, int end1, int end2){
Stack<Three<Integer, Integer, Integer>> stack = new Stack<Three<Integer, Integer, Integer>>();
stack.push(new Three<Integer, Integer, Integer>(begin1, end1, end2, 1));
int codeLoc = 1;
while (!stack.isEmpty()){
begin1 = stack.peek().getFirst();
end1 = stack.peek().getSecond();
end2 = stack.peek().getThird();
codeLoc = stack.peek().getLocation();
stack.pop();
if (begin1 < end2) {
switch (codeLoc){
case 1:
stack.push(new Three<Integer, Integer, Integer>(begin1, end1, end2, 2));
stack.push(new Three<Integer, Integer, Integer>(begin1, (end1 + begin1) / 2, end1, 1));
break;
case 2:
stack.push(new Three<Integer, Integer, Integer>(begin1, end1, end2, 3));
stack.push(new Three<Integer, Integer, Integer>(end1 + 1, (end2 + end1 + 1) / 2, end2, 1));
break;
case 3:
mergeUnit(array, begin1, end1, end2);
break;
}
}
}
};
private static void mergeSort(int[] array, final int begin1, final int end1,final int end2){
if (begin1 < end2) {
mergeSort(array, begin1, (end1 + begin1) / 2, end1);
mergeSort(array, end1 + 1, (end2 + end1 + 1) / 2, end2);
mergeUnit(array, begin1, end1, end2);
}
};
static private void mergeUnit(int[] array, final int begin1,final int end1,final int end2){
int[] mergeArr = new int[end2 - begin1 + 1];
int leftArrIndex = begin1;
int rightArrIndex = end1 + 1;
int mergeArrIndex = 0;
while (leftArrIndex <= end1 && rightArrIndex <= end2 ) {
if (array[leftArrIndex] < array[rightArrIndex]) {
mergeArr[mergeArrIndex++] = array[leftArrIndex++];
} else {
mergeArr[mergeArrIndex++] = array[rightArrIndex++];
}
} if (end1 < leftArrIndex){
while (rightArrIndex <= end2){
mergeArr[mergeArrIndex++] = array[rightArrIndex++];
}
}else if(end2 < rightArrIndex){
while (leftArrIndex <= end1){
mergeArr[mergeArrIndex++] = array[leftArrIndex++];
}
}
int m = 0;
for (int i = begin1; i <= end2; ++i, ++m){
array[i] = mergeArr[m];
}
}
}