java代替递归_Java将递归改成迭代的通⽤⽅法⽤Stack或LinkedList来实现内存中的出栈⼊栈过程，即可将递归改成循环。
第⼀个例⼦⽤求阶乘，顺便加了迭代⽅法。
import java.util.Stack;
public class Factorial{
public static void main(String[] args){
Factorial f = new Factorial();
System.out.ursion(5));
System.out.println(f.loop(5));
System.out.println(f.iteration(5));
}
/**
* 递归求阶乘
*/
public int recursion(int n){
if (n == 1) return 1;
return recursion(n-1) * n;
}
/**
* 循环求阶乘
*/
public int loop(int n){
Stack stack = new Stack();
nextint()方法
int result = 1;
stack.push(n);
while(!stack.isEmpty()){
n = stack.pop();
result *= n;
if (n > 1) stack.push(n-1);
}
return result;
}
/**
* 迭代求阶乘
*/
public int iteration(int n){
int result = 1;
for(int i = 1; i <= n; i++){
result *= i;
}
return result;
}
}
第⼆个例⼦是快速排序。递归快排⼤量数量时，容易爆栈。这时可以改成循环。import java.util.Random;
public class Sorts{
private static Random rand = new Random();
public static void main(String[] args){
int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,5,4,62
,99,98,54,56,17,18,23,34,15,35,25,53,51};
quickSort(a);
System.out.String(a));
int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,5,4,62
,99,98,54,56,17,18,23,34,15,35,25,53,51};
quickSortByLoop(a);
System.out.String(a));
}
/
**
* 快速排序
* 递归实现
*/
private static void quickSort(int[] arr, int start, int end){
if (start >= end) return;
int base = arr[start + Int(end-start+1)]; //中轴值
int left = start, right = end; //指⽰左右两端未排序的边界索引
int i = start; // ⽤于排序
while(i <= right){
if (arr[i] < base){ //⼩于中轴值则移到左侧
swap(arr, left++, i++);
}else if (arr[i] > base){ //⼤于中轴值则移到右侧
swap(arr, right--, i); //当前i位置的值未排序，故i不⾃增
}else{
i++;
}
}
//排完后left左侧均为⼩于base的数，right右侧均为⼤于base的数quickSort(arr, start, left-1);
quickSort(arr, right+1, end);
}
/**
* 快速排序
* 循环实现
*/
private static quickSortByLoop(int[] arr){
Stack stack = new Stack();
int start = 0;
int end = arr.length - 1;
stack.push(start);
stack.push(end);
while(!stack.isEmpty()){
end = stack.pop(); // 顺序很重要
start = stack.pop();
if (start < end){ // 开始排序
int i = start;
int base = arr[start + Int(end-start+1)]
int left = start;
int right = end;
while(i <= right){
if (arr[i] < base){
swap(arr, left++, i++);
}else if (arr[i] > base){
swap(arr, right--, i);
}else {
i++;
}
}
// ----右半边----
stack.push(right + 1);
stack.push(end);
// ----左半边----
stack.push(start);
stack.push(left - 1);
}
}
}
}
版权声明：本⽂为博主原创⽂章，未经博主允许不得转载。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。