计算上楼梯的方式数的递归解决方案

Question

我正在尝试用递归解决“计算到达楼梯第 n 步的方法”的问题。当给定一些要爬的楼梯时，我必须计算一次爬 1 步或 2 步的爬楼梯方式的数量。例如，如果有 4 个楼梯，我们将 return 5 因为我们将有：

我的代码当前抛出堆栈溢出异常：

 public static int countWaysToClimb(int stairs) {
     return countWaysToClimbHelper(stairs, 0, 0);
 }
 
 public static int countWaysToClimbHelper(int sumNeeded, int currentSum, int possibleCombos) {
     // base - we will reach this base multiple times
     if (sumNeeded == currentSum) {
         possibleCombos++;
         // if we already found a combo, we need to reset the sum
         countWaysToClimbHelper(sumNeeded,0,possibleCombos);  
     }
     
     else if (currentSum > sumNeeded) {
         return 0;
     }
     
     // recurse - add 1 and then add 2
     countWaysToClimbHelper(sumNeeded,currentSum+1,possibleCombos);  
     countWaysToClimbHelper(sumNeeded,currentSum+2,possibleCombos);
     return possibleCombos;             
 }

谢谢！

Answer 1

您的代码中存在一些问题：

基本情况（终止递归的条件）不正确。 递归调用的每个分支 在满足条件 if (sumNeeded == currentSum) is meat 而不是 returning 组合数时产生新的分支。您创建了一个不可避免地导致 WhosebugError 的无限递归。您必须在代码中第一个 if 之后的大括号内放置一个 return 语句。并注释掉第一个递归调用（将 0 总和作为参数传递）你将面临 第二个问题：对于任何输入，你的代码将产生 0.
由您的方法 countWaysToClimbHelper() 的 递归调用 编辑的结果 return 被省略。变量 possibleCombos 不受这些调用的影响。每个方法调用都会在堆栈（JVM 为每个方法调用存储数据的内存 aria）上分配此变量 possibleCombos 的副本，并且它们的值无论如何都不相关。
你实际上不需要将组合的数量作为参数传递，而是你有到return它。

在进一步讨论之前，让我回顾一下递归的基础知识。

每个递归方法都应该包含两部分:

基本案例 - 代表一个简单的 edge-case，其结果是预先知道的。对于这个问题，有两个edge-case：
- sumNeeded == currentSum - return 值为 1，即找到一个组合；
- sumNeeded > currentSum - return 值为 0.
recursive case - 解决方案的一部分，其中递归调用已完成并且主要逻辑所在。在你的递归情况下你需要累积组合数量的值，这将是值return的总和两个执行分支：采取 1 步 或 2 步.

因此固定代码可能如下所示：

public static int countWaysToClimb(int stairs) {
    return countWaysToClimbHelper(stairs, 0);
}

public static int countWaysToClimbHelper(int sumNeeded, int currentSum) {
    // base - we will reach this base multiple times
    if (sumNeeded == currentSum) {
        return 1;
    } else if (currentSum > sumNeeded) {
        return 0;
    }
    // recurse - add 1 and then add 2
    int possibleCombos = 0;
    possibleCombos += countWaysToClimbHelper(sumNeeded,currentSum + 1);
    possibleCombos += countWaysToClimbHelper(sumNeeded,currentSum + 2);
    return possibleCombos;
}

注：

此代码可以进一步增强。整个逻辑可以在 countWaysToClimb() 内实现，而无需使用 helper-method。为此，当递归调用方法时，您需要从 sumNeeded 中减去步数，而不是跟踪 currentSum。

计算上楼梯的方式数的递归解决方案

Recursive solution to counting the number of ways you can go up a staircase

java

recursion

stack-overflow

counting

recursive-backtracking