【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
前兩天上網的時候看到一個特別有意思的題目，在這裡和朋友們分享一下：
有一個人准備開始爬樓梯，假設樓梯有n個，這個人只允許一次爬一個樓梯或者一次爬兩個樓梯，請問有多少種爬法？
在揭曉答案之前，朋友們可以自己先考慮一下：
這個人爬n層樓梯，那麼它也不是一下子就可以爬這麼高的，他只有兩個選擇，要麼從n-2層爬過來，要麼從n-1層爬過來。除此之外，他沒有別的選擇。此時相信朋友其實已經早看出來了，這就是一道基本的遞歸題目。
（1）首先我們建立一個函數，判斷函數的合法性
void jump_ladder(int layer, int* stack, int* top)
{
if(layer <= 0)
return;
return;
}
void jump_ladder(int layer, int* stack, int* top)
{
if(layer <= 0)
return;
return;
}
（2）判斷當前的層數是為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;
}
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）對於2中提及的打印函數進行設計，代碼補全
#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);
}
#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）代碼中我們使用了宏，注意這是一個do{}while(0)的結構，同時我們對x進行了字符串強轉
b）當剩下台階為2的時候，此時有兩種情形，要麼一次跳完；要麼分兩次
（4）當階梯不為1或者2的時候，此時需要遞歸處理
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);
}
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);
}
祝：這裡在函數的結尾添加了一個函數，主要是遞歸的時候需要向堆棧中保存一些數據，為了代碼簡練，我們重新定義了一個函數。
總結：
1）這道題目和斐波那契數列十分類似，是一道地地道道的遞歸題目
2）遞歸的函數也需要好好測試，使用不當，極容易堆棧溢出或者死循環。對此，我們可以按照參數從小到大的順序依次測試，比如說，可以測試樓梯為1、2、3的時候應該怎麼運行，同時手算和程序相結合，不斷修正代碼，完善代碼。
