[C] 계단 오르는 방법의 가짓수 (재귀함수)

한번에 1칸, 2칸 혹은 3칸씩 올라갈 수 있음.

n개의 계단이 있을때 올라가는 방법의 가짓수

#include<stdio.h>
 
// 재귀함수
int stair(int n) {                   // f(n) = f(n - 1) + f(n - 2) + f(n - 3) 규칙이 사용 
    if (n == 1)
        return 1;
    else if (n == 2)
        return 1 + stair(1);
    else if (n == 3)
        return 1 + stair(1) + stair(2);
    else
        return stair(n - 3) + stair(n - 2) + stair(n - 1);
}

int main() {
    int num;
    printf("n=? ");
    scanf_s("%d", &num);
    printf("%d \n", stair(num));  //함수 호출
}