通过递归的方式可以比较容易的得到结果：下面是程序代码
[java]
public class StepDemo {
private static int sum = 2;//总的台阶数
public static void main(String[] args) {
step(sum,"");
}
private static void step(int subsum,String result){
if(subsum<=0){
System.out.println(result);
return;
}
if(subsum==1){
step(subsum-1,result+1);
}
if(subsum>1){//有两种可以选
int j=1;
for(;j<=2;j++){
step(subsum-j,result+j);
}
}
}
}
public class StepDemo {
private static int sum = 2;//总的台阶数
public static void main(String[] args) {
step(sum,"");
}
private static void step(int subsum,String result){
if(subsum<=0){
System.out.println(result);
return;
}
if(subsum==1){
step(subsum-1,result+1);
}
if(subsum>1){//有两种可以选
int j=1;
for(;j<=2;j++){
step(subsum-j,result+j);
}
}
}
}
不是很复杂，但是有一个容易出现的问题：如果我们把程序写成如下形式：
[java]
public class StepDemo {
private static int sum = 2;//总的台阶数
public static void main(String[] args) {
step(sum,"");
}
private static void step(int subsum,String result){
if(subsum<=0){
System.out.println(result);
return;
}
if(subsum==1){
result = result+1;
step(subsum-1,result);
}
if(subsum>1){//有两种可以选
int j=1;
for(;j<=2;j++){
result = result+j;
step(subsum-j,result);
}
}
}
}
public class StepDemo {
private static int sum = 2;//总的台阶数
public static void main(String[] args) {
step(sum,"");
}
private static void step(int subsum,String result){
if(subsum<=0){
System.out.println(result);
return;
}
if(subsum==1){
result = result+1;
step(subsum-1,result);
}
if(subsum>1){//有两种可以选
int j=1;
for(;j<=2;j++){
result = result+j;
step(subsum-j,result);
}
}
}
}上面的程序中我们希望找到在m=2时的所有的方案。程序结果为：
[html]
11
12
11
121+2=3，这样就走了3层，而m=2，这必然是不对的。这是什么原因呢：
我们看当subsum=2时，满足subsum>2，进入for循环
[java]
j=1--->第一次调用的step中的result=“1”--->step(1,"1")||||递归调用，满足subsum=1，第二次调用的step中的result=“11”|||递归调用--->输出11
j=1--->第一次调用的step中的result=“1”--->step(1,"1")||||递归调用，满足subsum=1，第二次调用的step中的result=“11”|||递归调用--->输出11[java] view plaincopyprint j=2--->第一次调用的step中的result已经是"1"了，现在要执行
result = result+j;得到的result就是“12”了而正确代码中没有直接改变本层递归中result的值