c++ - 不理解为什么这个 C++ 递归函数起作用背后的逻辑

Question

此函数旨在生成上楼梯的大步和小步的组合数(用户给定的值)。小步走 1 步，大步走 2 步。

但是，我不明白这里使用的递归见解。我真的很感激解释为什么这会产生所需的组合数量。通过它，我可以看到它有效，但我不确定我自己是如何得出这个逻辑的。

有人可以阐明这一点吗？

代码如下:

int CountWays(int numStairs);
int combination_strides = 0;
const int LARGE_STEP = 2;
const int SMALL_STEP = 1;

int main() {

    cout << "Enter the number of stairs you wish to climb: ";
    int response = GetInteger();
    int combinations = CountWays(response);
    cout << "The number of stride combinations is: " << combinations << endl;

    return 0;
}


int CountWays(int numStairs) {

    if (numStairs < 4) {
    return numStairs;

    } else {
    return CountWays(numStairs - SMALL_STEP) + CountWays(numStairs - LARGE_STEP);

    }
}

Answer 1

要下numStairs，您可以:

• 走一小步，然后向下(numStairs - SMALL_STEP)；或
• 迈一大步，然后向下(numStairs - LARGE_STEP)。

所以总的方法数是向下的方法数 (numStairs - SMALL_STEP) 和向下的方法数 (numStairs - LARGE_STEP)，因此递归。

可以很简单地看出，有一种方法可以下降一步 (S)，有两种方法可以下降两步(SS 或 L)，三种可以下降三步(SSS、SL 或 LS)，因此是终止条件。

您可能将此递归识别为 Fibonacci sequence 的定义.对于奖励积分，您可能希望重组计算，使其以线性时间而不是指数时间运行。