楼主，我刚测试了一下，你的那个边界条件错了。
a(1) = 1 b(1) = 0
a(2) = 1 b(2) = 1

我的代码是：

/* ----递推 
设上到第n级台阶走奇数步的走法为a(n)，走偶数步的走法为b(n)。那么，
a(n) = b(n-1) + b(n-2)
b(n) = a(n-1) + a(n-2)
边界条件
a(1) = 1 b(1) = 0
a(2) = 1 b(2) = 1
题目要的结果是b(39)
*/
#include <stdio.h>
int EvenStep(int even);

int OddStep(int odd){   //奇数 
    if( odd == 1){
        return 1;
    } 
    if(odd == 2){
        return 1;
    }
    
    return EvenStep(odd-1) + EvenStep(odd-2);
}

int EvenStep(int even){  //偶数 
    if( even == 1 ){
        return 0;
    }
    if( even == 2){
        return 1;
    }
    
    return OddStep(even-1) + OddStep(even-2);
} 

int main(){
    printf("%d\n", EvenStep(39));//总步数为偶数
    
    return 0;
} 

 如果有错误，希望指出，谢谢