java - 为什么递归代码没有调用所有情况？

Question

我目前是一名学习递归的新手程序员，我不明白为什么我的代码不起作用。我必须编写一个名为waysToClimb 的递归方法，它输出爬n 步的不同方法。您可以 1 步爬 1 或 2 级台阶。这是我到目前为止所拥有的:

public void waysToClimb(int n) {
  if (n == 0) {
    //base case, makes a new line for the next series of steps 
    System.out.println();
  }
  if (n >= 1) {
    //1 step, prints 1 and subtracts 1 from n
    System.out.print("1 ");
    waysToClimb(n - 1);
  }
  if (n >= 2) {
    //2 steps, prints 2 and subtracts 2 from n
    System.out.print("2 ");
    waysToClimb(n - 2);
  }
}

我的问题是，当步数大于 2 时，当 n >= 2 的 if 语句仅输出 2，而没有其他数字。例如，casewaysToClimb(3)打印出:

1 1 1  
2 (should be 1 2)  
2 1  

为什么不打印出 1 2？我的 if 语句不应该打印出所有可能的组合吗，因为代码被迫检查每一个组合

Answer 1

标记代码并逐步执行:

public void waysToClimb(int n) {
  // #1
  if (n == 0) {   
    //base case, makes a new line for the next series of steps 
    System.out.println();
  }
  // #2
  if (n >= 1) {
    //1 step, prints 1 and subtracts 1 from n
    System.out.print("1 ");
    waysToClimb(n - 1);
  }
  // #3
  if (n >= 2) {
    //2 steps, prints 2 and subtracts 2 from n
    System.out.print("2 ");
    waysToClimb(n - 2);
  }
}

您的代码现在逐步执行的操作:

Call:          IF:    Print:      Function call:
waysToClimb(3) #2     1           waysToClimb(2)
waysToClimb(2) #2     1           waysToClimb(1)
waysToClimb(1) #2     1           waysToClimb(0)
waysToClimb(0) #1     \n          return
waysToClimb(2) #3     2           waysToClimb(0)
waysToClimb(0) #1     \n          return
waysToClimb(3) #3     2           waysToClimb(1)
waysToClimb(1) #2     1           waysToClimb(0)
waysToClimb(0) #1     \n          return

因此输出是:

1 1 1
2
2 1

你应该做什么:

public void waysToClimb(int n, String s) {
  if (n == 0) {
    System.out.println(s);
  }
  if (n >= 1) {
    waysToClimb(n - 1, s + "1 ");
  }
  if (n >= 2) {
    waysToClimb(n - 2, s + "2 ");
  }
}    

调用该函数:

 waysToClimb(3, "");