不理解为什么这个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序列的定义.对于奖励积分,您可能希望重新计算计算,使其以线性而非指数时间运行.