递归与递推的解法（c++）

解题思路:本题解有两种解题思路，利用递推与递归的解决方法

主要公式：f(n) = f(n - 1) + f(n - 3)

注意事项:另外递归的方法对于本题时间要求是超时的，仅供参考学习
参考代码:

递推：

#include <iostream>
using namespace std;

int main(){
    int n;
    int a[55] = {0,1, 2, 3 ,4};
    for(int i = 5 ; i <= 55 ;i++){
        a[i] = a[i - 1] + a[i - 3];
    }
    while(cin >> n){
        if(n == 0) return 0;
        cout << a[n] << endl;
    }
    return 0;
}

递归：（超时）

#include <iostream>
using namespace std;

int dfs(int n){
    if(n <= 4) return n;
    else if(n >= 5 && n <= 55)
    return dfs(n - 1 ) + dfs( n - 3);
}

int main(){
    long long int x;
    while(scanf("%d\n" , &x)){
        if (x == 0) break;
        printf("%d\n", dfs(x));
    }
    return 0;
}