前言：我们习惯了使用递归算法来解决一些常见的问题：例如阶乘、Fibonacci数列、汉诺塔等问题，可在实际中或者在面试中我们可能碰到一些BT的题目，要求你用非递归算法实现一些常见的递归问题。今天，我们将对这一问题进行一个小小的讨论。
1.递归相关
递归函数(recursive function)是直接调用自己或通过另一函数间接调用自己的函数。调用递归函数解决问题时，函数实际上只知道解决基本情况，对基本情况的函数调用只是简单地返回一个结果。如果在更复杂的问题中调用函数，则函数将问题分成两个概念性部分：函数中能够处理的部分和函数中不能够处理的部分。要让递归最终停止，每次函数调用是都使问题进一步简化，从而产生越来越小的问题，最终合并到基本情况。
2.阶乘的递归与非递归
阶乘我们编码时一般采用递归算法，其参考实现如下：
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.regex.Pattern;
* Create Time： 2007-11-22 下午02:31:36
* FileName: Factorial2.java
*/
public class Factorial2 {
public static void main(String[] args) {
int number = 0;
String readline = "";
System.out.print("Enter a Positive number(0~20): ");
BufferedReader input = new BufferedReader(new InputStreamReader(
System.in));
try {
readline = input.readLine();
} catch (Exception ex) {
ex.printStackTrace();
}
if (!Pattern.matches("^[0-9]*$", readline)) { // 正则表达式匹配非负数
System.out.println("Please enter a number!");
} else {
number = Integer.parseInt(readline);
Factorial2 fac = new Factorial2();
System.out.println("the " + number + "'s Factorial is "
+ fac.getFactorial(number));
}
}
public long getFactorial(int num) {
long result = 0;
if (num == 0 || num == 1) {
result = 1;
} else {
result = num * getFactorial(num - 1); //递归的使用
}
return result;
}
}
由上面可以看出，递归实际上采用的是一种自顶向下的方法，直到方法知道如何解决最简单的问题。同时在递归的过程中，递归算法需要一个线性的空间开销，并且需要不断的压栈与出栈。一般来讲，非递归算法的资源开销比递归算法低。那么，我们如何实现阶乘的非递归的算法呢？我们只需要反过来想，既然递归采用的是自顶向下的方法，那么我们非递归就可以采用自底向上的方法来实现。参考代码如下：
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.regex.Pattern;
/**
* @author jefferent@tom.com
* @version Create Time： 2007-11-21 下午10:23:46
* FileName: Factorial.java
*/
public class Factorial {
public static void main(String[] args)
{
int number = 0;
String readline = "";
System.out.print("Enter a Positive number(0~20): ");
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
try{
readline = input.readLine();
}catch(Exception ex){
ex.printStackTrace();
}
if(!Pattern.matches("^[0-9]*$",readline)){ //正则表达式匹配非负数
System.out.println("Please enter a number!");
}
else{
number = Integer.parseInt(readline);
Factorial fac = new Factorial();
fac.getFactorial(number);
}
}
public void getFactorial(int num){
long firstnum = 1;
long secondnum = 2;
long result = 0;
if(num == 0 || num == 1){
result = 1;
}
else {
int flag = num;
while(flag > 1){
result = firstnum * secondnum; //非递归实现阶乘
firstnum = result;
secondnum = secondnum + 1;
flag--;
}
}
System.out.println("the "+num+"'s Factorial is " + result);
}
}
分析代码我们知道，非递归的实现是一个循环，从最简单的开始算起，并将每次计算的结果赋给一个乘数，另一个乘数加1后再次进行计算，当条件不满足时计算完毕，最终得到result就是计算结果。
3.Fibonacci数列的递归和非递归
//非递归方法
public class Fibonacci1{
//用非递归方法打印fibonacci数列的前50项
public static void main(String[] args) {
long ff = 1;
long fs = 1;
System.out.println(ff);
for(int i = 0; i < 50; i++){
System.out.println(fs);
fs = fs + ff ;
ff = fs - ff ;
}
}
}
//递归方法
public class Fibonacci2 {
//用递归方法打印fibonacci数列的前50项
public static void main(String[] args) {
for(int i = 0; i < 50; i++){
System.out.println(fib(i));
}
}
private static long fib(int n){
if( (n == 0) || (n == 1) ) return 1;
return (fib(n-2) + fib(n-1));
}
}
4.汉诺塔的递归和非递归
以下代码来源于网络
//递归汉诺塔
/**
* Classname: HanoiRecursion
* @version 1.0
* Created on 2005-4-20
* Company: Berheley Technology Co.,Ltd.
*/
/**
* @author yingbing wu
*
*/
public class HanoiRecursion {
public static void move(int n, String from, String to, String mid) {
if (n < 1)
System.out.println("Plate number can't less than 1");
else {
if (n == 1)
System.out.println("plate: " + n + " " + from + "->" + to);
else {
move(n - 1, from, mid, to);
System.out.println("plate: " + n + " " + from + "->" + to);
move(n - 1, mid, to, from);
}
}
}
public static void main(String[] args) {
int n;
if (args.length > 0)
n = Integer.parseInt(args[0]);
else
n = 5;
for (int i = 1; i <= n; i++) {
move(i, "A", "C", "B");
System.out.println();
}
}
}
//非递归汉诺塔
/**
* Classname: Hanoi
* @version 1.0
* Created on 2005-4-20
* Company: Berheley Technology Co.,Ltd.
*/
public class HanoiNoRecursion {
public static void main(String[] args) {
int n;
if (args.length > 0)
n = Integer.parseInt(args[0]);
else
n = 5;
for (int i = 1; i <= n; i++) {
hanoi(i);
System.out.println();
}
}
public static void hanoi(int n) {
String[] move = { "B->C", "C->A", "A->B", "C->B", "A->C", "B->A",
"C->B", "B->A", "A->C", "B->C", "A->B", "C->A" };
if (n < 1)
return;
boolean[] bit = new boolean[n];
int i, j = 0, k;
for (i = 0; i < n; i++)
bit[i] = false;
while (true) {
j++;
j = j % 3;
for (i = 0; i < n && bit[i]; i++)
bit[i] = false;
if (i == n)
break;
bit[i] = true;
k = (j + 3) - (i % 2) * 3 + 6 * ((n - 1) % 2); // **fill an expression here！**
System.out.println("plate: " + (i + 1) + " " + move[k]);
}
}
}
