递归函数-楼梯

Question

我一直专注于递归函数，并在网上搜索了一些问题，以了解它们是如何工作的。我遇到了一个叫做楼梯的问题，这是为它设计的代码-

#include<bits/stdc++.h>

using namespace std;

int staircase(int n){
    if(n<0){            //Base Case 1
        return 0;
    }

    if(n==0){           //Base Case 2
        return 1;
    }

    int count = 0;
    count += staircase(n-1);    //Stepping 1 step
    count += staircase(n-2);    //Stepping 2 step
    count += staircase(n-3);    //Stepping 3 step

    return count;
}

int main(){
    int n;
    cout<<"Enter number of stairs\n";

    cin>>n;

    cout<<"No of ways to climb stairs are ";
    cout<<staircase(n)<<endl;

    return 0;
}

如果有人能帮我从“int count”{I have understand the base cases}理解阶梯函数，那将非常有帮助！

Answer 1

在每次函数调用中，您都需要爬n个楼梯。在一次尝试中，你可以爬一个楼梯、两个楼梯或三个楼梯。因此，您使用n=n-1再次调用该函数，并将其结果添加到计数中。这个调用表示您只爬了一个楼梯（还有n-1个楼梯要爬）。同样，您可以添加爬2个楼梯后可能的方式数（n=n-2）和爬3个楼梯后可能的方式数（n=n-3）。注意，这个函数是指数函数，如果n是一个大数字，则需要很长时间。你可以通过使用记忆来解决这个问题。

#include<bits/stdc++.h>

using namespace std;

const int MAX_SIZE = 100;

long long mem[MAX_SIZE];

int staircase(int n){
    if(n<0){            //Base Case 1
        return 0;
    }

    if(n==0){           //Base Case 2
        return 1;
    }

    if (mem[n] != -1)
        return mem[n];

    int count = 0;
    count += staircase(n-1);    //Stepping 1 step
    count += staircase(n-2);    //Stepping 2 step
    count += staircase(n-3);    //Stepping 3 step

    return mem[n] = count;
}

int main(){

    for (int i = 0; i < MAX_SIZE; i++)
        mem[i] = -1;

    int n;
    cout<<"Enter number of stairs\n";

    cin>>n;

    cout<<"No of ways to climb stairs are ";
    cout<<staircase(n)<<endl;

    return 0;
}

这是使用memoization后的代码。请注意，如果没有记忆，计算所需的时间将非常长。例如，尝试使用n=50运行代码，并使用此代码进行尝试。还要注意的是，即使可以将MAX_SIZE设置为100000左右，在n=100之前，结果也会非常大。如果您真的想计算n的大值的结果，可以使用所谓的“大整数”。

Answer 2

从本质上讲，这段代码试图找到可以到达步骤n的方法。如果可以执行步骤1、2或3，则可以从步骤n-1、n-2和n-3到达步骤n。因此，到达步骤n的方法数是到达步骤n-1、n-2和n-3的方法数之和。代码使用递归来实现这一点，通过使用不同的步长调用自身3次。