Рекурсивные функции - Лестница

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» {Я понял основу дела}!

Answer 1

При каждом вызове функции вам нужно подняться по лестнице n. За одну попытку вы можете подняться на одну, две или три ступеньки. Итак, вы снова вызываете функцию с помощью n = n - 1 и добавляете ее результат к count. Этот вызов означает случай, когда вы поднялись только на одну ступеньку (осталось подняться 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;
}

Вот код после использования памятки. Обратите внимание, что без напоминания время вычислений будет очень долгим. Попробуйте запустить код с n = 50, например, и попробуйте его с этим кодом. Также обратите внимание, что даже если вы можете установить MAX_SIZE примерно на 100 000, результат будет очень большим, прежде чем даже n = 100. Если вы действительно хотите рассчитать результат для больших значений n, вы можете использовать так называемые «большие целые числа».

Answer 2

По сути, этот код пытается найти, сколько способов вы можете сделать, чтобы перейти к шагу n. Если вы можете выполнить шаг 1, 2 или 3 шага, то вы можете перейти к шагу n из шагов n-1, n-2 и n-3. Следовательно, количество способов добраться до этапа n является суммой количества способов добраться до этапов n-1, n-2 и n-3. Код использует рекурсию для выполнения sh этого, путем вызова себя 3 раза с разными номерами шагов.