遞廻的優化

剪枝

#

在這個章節中，我們將討論如何在遞迴函式中使用剪枝技巧來優化遞迴函式的效率。

剪枝是指在遞迴函式中，提早 return 的技巧。這樣可以減少遞迴的深度，從而提高遞迴函式的效率。

但是在大部分情況下，剪枝技巧的複雜度通常難以估計。不過有少部分情境比較特殊或奇怪的限制問題是還可以透過剪枝技巧來達到實質優化複雜度的效果。

例題

#

以上一個章節的問題為例，我們先來觀察看看遞迴樹的結構。

根據題敘，我們可以知道每個集合中的數字都是正整數，所以如果 \(x\) 是 \(12\) 的話，其實任何已經大於 \(12\) 的節點都不需要再往下遞迴了，因為這樣的結果一定不會是答案。

紅色圈起來的區塊都是可以直接省略的，可能這張圖中看不出太大的優化效果，但是如果集合更多且集合中的數字更多的話，這樣的剪枝效果就會非常明顯。

實作

#

實作上，我們只需要在遞迴函式的開頭加上一個判斷式，如果目前的乘積已經大於 \(x\) 的話就直接 return 即可。

void rec(int i, int val) {
    if (val > x) return; // 剪枝
    if (i == n) {
        if (val == x) ans++;
        return;
    }
    for (int j = 0; j < a[i]; j++) {
        rec(i + 1, val * a[i][j]);
    }
}

在不同的問題中，剪枝的方式可能會有所不同，可以根據題目的特性來設計剪枝的方式！