递归算法2

import java.util.ArrayList;
import java.util.List;

public class TestAG {
public static List<String> list = new ArrayList<String>();
public static long count = 0l;
// 初始字符串
public static String gstr = "aaaa";
public static String endStr = "";

/**
* @param args
*/
public static void main(String[] args) {
for (int i = 0; i < gstr.length(); i++) {
endStr = "f" + endStr;
}
// 递归调用change
change(gstr, gstr.length());
// 打印调用次数
System.out.println(count);
}

public static void change(String str, int lenth) {
//满足结束条件时退出。"ffffff...."
if (str.equals(endStr)) {
return;
} else {
//在末尾加一。add方法内部也递归调用，进行进位。如从aaff变到abaa。
String addResult = add(str, lenth - 1);
//递归调用change方法
change(addResult, lenth);
}
}

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 + 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;
}
}