前兩天上網(wǎng)的時(shí)候看到一個(gè)特別有意思的題目，在這里和朋友們分享一下：

有一個(gè)人準(zhǔn)備開(kāi)始爬樓梯，假設(shè)樓梯有n個(gè)，這個(gè)人只允許一次爬一個(gè)樓梯或者一次爬兩個(gè)樓梯，請(qǐng)問(wèn)有多少種爬法？

在揭曉答案之前，朋友們可以自己先考慮一下：

這個(gè)人爬n層樓梯，那么它也不是一下子就可以爬這么高的，他只有兩個(gè)選擇，要么從n-2層爬過(guò)來(lái)，要么從n-1層爬過(guò)來(lái)。除此之外，他沒(méi)有別的選擇。此時(shí)相信朋友其實(shí)已經(jīng)早看出來(lái)了，這就是一道基本的遞歸題目。

（1）首先我們建立一個(gè)函數(shù)，判斷函數(shù)的合法性

void jump_ladder(int layer, int* stack, int* top)
{
    if(layer <= 0)
        return;

    return;
}

（2）判斷當(dāng)前的層數(shù)是為1或者是否為2

void jump_ladder(int layer, int* stack, int* top)
{
    if(layer <= 0)
        return;

    if(layer == 1){
        printf_layer_one(layer, stack, top);
        return;
    }

    if(layer == 2){
        printf_layer_two(layer, stack, top);
        return;
    }

    return;
}

（3）對(duì)于2中提及的打印函數(shù)進(jìn)行設(shè)計(jì)，代碼補(bǔ)全

#define GENERAL_PRINT_MESSAGE(x)
    do {
        printf(#x);
        for(index = (*top) - 1 ; index >= 0; index --)
            printf("%d", stack[index]);
        printf("n");
    }while(0)

void printf_layer_one(int layer, int* stack, int* top)
{
    int index ;
    GENERAL_PRINT_MESSAGE(1);
}

void printf_layer_two(int layer, int* stack, int* top)
{
    int index;

    GENERAL_PRINT_MESSAGE(11);
    GENERAL_PRINT_MESSAGE(2);
}

注：

a）代碼中我們使用了宏，注意這是一個(gè)do{}while(0)的結(jié)構(gòu)，同時(shí)我們對(duì)x進(jìn)行了字符串強(qiáng)轉(zhuǎn)

b）當(dāng)剩下臺(tái)階為2的時(shí)候，此時(shí)有兩種情形，要么一次跳完；要么分兩次

（4）當(dāng)階梯不為1或者2的時(shí)候，此時(shí)需要遞歸處理

void _jump_ladder(int layer, int* stack, int* top, int decrease)
{
    stack[(*top)++] = decrease;
    jump_ladder(layer, stack, top);
    stack[--(*top)] = 0;
}

void jump_ladder(int layer, int* stack, int* top)
{
    if(layer <= 0)
        return;

    if(layer == 1){
        printf_layer_one(layer, stack, top);
        return;
    }

    if(layer == 2){
        printf_layer_two(layer, stack, top);
        return;
    }

    _jump_ladder(layer- 1, stack, top, 1);
    _jump_ladder(layer- 2, stack, top, 2);
}

祝：這里在函數(shù)的結(jié)尾添加了一個(gè)函數(shù)，主要是遞歸的時(shí)候需要向堆棧中保存一些數(shù)據(jù)，為了代碼簡(jiǎn)練，我們重新定義了一個(gè)函數(shù)。

總結(jié)：

1）這道題目和斐波那契數(shù)列十分類似，是一道地地道道的遞歸題目

2）遞歸的函數(shù)也需要好好測(cè)試，使用不當(dāng)，極容易堆棧溢出或者死循環(huán)。對(duì)此，我們可以按照參數(shù)從小到大的順序依次測(cè)試，比如說(shuō)，可以測(cè)試樓梯為1、2、3的時(shí)候應(yīng)該怎么運(yùn)行，同時(shí)手算和程序相結(jié)合，不斷修正代碼，完善代碼。