第三十九级台阶问题，递归，斐波那契

问题遇到的现象和发生背景

刷题时遇到这个题目，我想了想，这就是斐波那契的变种，于是就自己写了，然后就出问题了

问题相关代码，请勿粘贴截图

public class 第三十九级台阶 {
static int count;
public static void main(String[] args) {
int n=39;
int sum=fib(n);
System.out.println(sum);
}

public static int fib(int n){
    if(n==2) return 1;
    if(n==3) return 2;
    if(n==4) return 2;
    if(n==5) return 4;
    return fib(n-2)+fib(n-3)+fib(n-4);
}

}

运行结果及报错内容

我的答案是7位数，1587660，然而答案是一个八位数51167078

我的解答思路和尝试过的方法

既然要求是偶数步了，那我不妨把左右步合并为一个大步，每走两步为一个大步。
走一次大步，可能出现走两层、三层、四层的情况。于是递归的是三个相加

我想要达到的结果

跟答案一样是八位数

public class Main {
    static int ans;
    static void f(int n,int steps) {
        if(n<0)return;//这个边界必须写
        if(n==0) {
            if(steps%2==0)//满足条件，ans++
            ans++;
            return;
        }
        f(n-1,steps+1);//必须写steps+1，不能写成steps++
        f(n-2,steps+1);
    }
    
    public static void main(String[] args) {
        f(39,0);//调用函数
        System.out.println(ans);//输出
    }
}

其他方法，网上也是有的。
只是我想把这个思路弄会，知道这种方法在逻辑上哪里错了。
不然以后再遇到类似的问题，或者算法考试的时候遇到了，总不能现场“求助诸贤”吧