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

Question

我试图用递归解决“计算到达楼梯第 n 级台阶的方法”的问题。当给定多个要爬的楼梯时，我必须计算一次爬 1 步或 2 步的攀登方式的数量。例如，如果有 4 个楼梯，我们将返回 5，因为我们会：

  * 1 1 1 1
  * 1 1 2
  * 1 2 1
  * 2 1 1
  * 2 2

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

 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 eat 时生成新分支，而不是返回组合数。您创建了无限递归，这不可避免地会导致 StackOverflowError。您必须在代码中第一个 if 之后的大括号内放置 return 语句。并注释掉第一个递归调用（将 0 sum 作为参数传递），您将面临第二个问题：对于任何输入，您的代码将产生 0。
• 方法 countWaysToClimbHelper() 的递归调用返回的结果将被忽略。变量 possibleCombos 不受这些调用的影响。每个方法调用都会在堆栈（JVM 为每个方法调用存储数据的内存区域）上分配该变量possibleCombos 的自己的副本，并且它们的值无论如何都不相关。
• 实际上，您不需要将组合数量作为参数传递，而是需要返回它。

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

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

• 基本情况 - 表示提前知道结果的简单边缘情况。对于这个问题，有两种边缘情况：
  • sumNeeded == currentSum - 返回值为1，即找到一个组合；
  • 所需总和> currentSum - 返回值为0。
• 递归案例 - 解决方案的一部分，其中递归调用以及主逻辑所在。在您的递归情况中，您需要累积组合数量的值，这将是两个执行分支返回的值的总和：采取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() 内部实现，而无需使用辅助方法。为此，您需要在递归调用该方法时从 sumNeeded 中减去步数，而不是跟踪 currentSum。