递归算法1

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;

public class TestAF {
public static List<String> list = new ArrayList<String>();
public static BigDecimal count = new BigDecimal(0).setScale(0);
// 初始字符串.长度为10时，不打印结果，纯运行程序的时间是34秒。进行了60466175次计算。
//长度每再增加1，时间约增长6倍
//如果在控制台打印结果的话，时间再增长很多倍。
public static String gstr = "aaaaaa";

/**
* @param args
*/
public static void main(String[] args) {
//可删除，调试用
System.out.println(new Date());



String endStr="";
for (int i = 0; i < gstr.length(); i++) {
endStr = "f" + endStr;
}
String ret=gstr;
//递归调用change,满足结束条件时退出。"ffffff...."
while(!ret.equals(endStr)){
ret = change(ret, ret.length());
}


//可删除，调试用
// 打印调用次数
System.out.println(count);
System.out.println(new Date());


}

public static String change(String str, int lenth) {

//在末尾加一。add方法内部也递归调用，进行进位。如从aaff变到abaa。
String addResult = add(str, lenth - 1);
//递归调用change方法
return addResult;
}

public static String add(String str, int index) {
//index<0 时退出。
if (index < 0) {
System.out.println("index<0" + str);
return str;
} else {
int tmp = (int) str.charAt(index);
//index位加1
tmp++;
//加一后如果是g,则转变为a，并且index减一,递归调用add方法，在index-1位置加1来进位.
//如从aaff ->  aafa  ->  aaaa  ->abaa
if (tmp == 103) {
tmp = 97;
//字符串重新组合。更新index位置的字符。
String conResult = conStr(str, index, tmp);
//进位
index--;
return add(conResult, index);
} else {
String ss2 = conStr(str, index, tmp);
//计数，调试用。可删掉。
count = count.add(new BigDecimal(1));
//打印结果
System.out.println(ss2);
//返回结果
return ss2;
}
}
}

public static String conStr(String str, int index, int tmp) {
//替换index位置的字符
String ss1 = "";
if (index == str.length() - 1) {
ss1 = str.substring(0, index) + (char) tmp;
} else {
ss1 = str.substring(0, index) + (char) tmp
+ str.substring(index + 1);
}
return ss1;
}
}