我正在嘗試通過遞回解決“計算到達樓梯第 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;
}
謝謝！
uj5u.com熱心網友回復：
您的代碼中存在一些問題：
- 基本情況（終止遞回的條件）不正確。遞回呼叫的每個分支在滿足條件時都會產生新的分支，
if (sumNeeded == currentSum)而不是回傳組合的數量。您創建了一個無限遞回，不可避免地導致StackOverflowError. 您必須在代碼中第一個之后的大括號內放置一個returnif陳述句。并注釋掉第一個遞回呼叫（將0sum 作為引數傳遞），您將面臨第二個問題：對于任何輸入，您的代碼都會產生0。 - 方法的遞回呼叫回傳的結果將
countWaysToClimbHelper()被省略。變數possibleCombos不受這些呼叫的影響。possibleCombos每個方法呼叫都會在堆疊（JVM 為每個方法呼叫存盤資料的記憶體 aria）上分配它自己的這個變數的副本，并且它們的值無論如何都不相關。 - 您實際上不需要將組合數作為引數傳遞，而是必須回傳它。
在進一步討論之前，讓我回顧一下遞回的基礎知識。
每個遞回方法都應該包含兩部分：
- 基本情況- 表示一個簡單的邊緣情況，其結果是預先知道的。對于這個問題，有兩種極端情況：
sumNeeded == currentSum- 回傳值為1，即找到一個組合；sumNeeded > currentSum- 回傳值為0.
- 遞回案例- 解決方案的一部分，其中遞回呼叫和主邏輯駐留。在您的遞回情況下，您需要累積組合數的值，這將是兩個執行分支回傳的值的總和：采取1 step或2 steps。
所以固定的代碼可能看起來像這樣：
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()不使用輔助方法的情況下在內部實作。為此，currentSum您需要從sumNeeded遞回呼叫方法時減去步驟數，而不是跟蹤。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/439502.html
上一篇：問題直觀理解爬樓梯問題的解法，為什么不是t(n-1) t(n-2)不是t(n)=t(n-1) t(n-2) 2？