棧與遞歸

棧還有一個(gè)重要應(yīng)用是在程序設(shè)計(jì)語(yǔ)言中實(shí)現(xiàn)遞歸。一個(gè)直接調(diào)用自己或通過(guò)一系列的調(diào)用語(yǔ)句間接的調(diào)用自己的函數(shù)，稱為遞歸函數(shù)。

遞歸是程序設(shè)計(jì)中一個(gè)強(qiáng)有力的工具。
其一，有很多數(shù)學(xué)函數(shù)是遞歸定義的，如大家熟悉的階乘函數(shù)：

2階Fibonacci數(shù)列：

Ackerman函數(shù)：

其二，有的數(shù)據(jù)結(jié)構(gòu)，如二叉樹、廣義表等，由于結(jié)構(gòu)本身固有的遞歸特性，則它們的操作可遞歸的描述；
其三，還有一類問(wèn)題，雖然問(wèn)題本身沒(méi)有明顯的遞歸結(jié)構(gòu)，但用遞歸求解比迭代求解更簡(jiǎn)單，如八皇后問(wèn)題、Hanoi塔問(wèn)題。

n階Hanoi塔問(wèn)題：
假設(shè)有3個(gè)分別命名為X、Y、Z的塔座，在塔座X上插有n個(gè)直徑大小各不同、依小到大編號(hào)為1，2，...，n的圓盤。現(xiàn)要求將X軸上的n個(gè)圓盤移至塔座Z上并仍按同樣順序疊排，圓盤移動(dòng)時(shí)必須遵循下列規(guī)則：
1.每次只能移動(dòng)一個(gè)圓盤
2.圓盤可以插在X 、Y、Z中的任一塔座上
3.任何時(shí)刻都不能將一個(gè)較大的圓盤壓在較小的圓盤上。

如何實(shí)現(xiàn)移動(dòng)圓盤的操作呢?
當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)單，只要將編號(hào)為1的圓盤從塔座X直接移至塔座Z上即可；

當(dāng)n>1時(shí)，需利用塔座Y作為輔助塔，若能設(shè)法將壓在編號(hào)為n的圓盤之上的n-1個(gè)圓盤從塔座X移至塔座Y上，則可先將編號(hào)為n的圓盤從塔座X移至塔座Z上，然后再將塔座Y上的n-1個(gè)圓盤移至塔座Z上。

而如何將n-1個(gè)圓盤從一個(gè)塔座移至另一個(gè)塔座的問(wèn)題是一個(gè)和原問(wèn)題具有相同特征屬性的問(wèn)題，只是問(wèn)題的規(guī)模小1，因此可以用同樣的方法求解。

TowerOfHanoi.c利用了前面的C封裝的順序棧對(duì)象 用線性表表示的順序棧
實(shí)現(xiàn)了Hanoi塔遞歸移動(dòng)的過(guò)程，每一步執(zhí)行的過(guò)程以及x、y、z三個(gè)軸的狀態(tài)均可以看到。

github源碼

TowerOfHanoi.c文件

#include <stdio.h>
#include <malloc.h>
#include "LinearListStack.h"

void hanoi(int n,LinearListStack *x,LinearListStack *y,LinearListStack *z){
    char elem;
    if(n == 1){
        x->pop(x,&elem);
        z->push(z,&elem); //將編號(hào)為1的圓盤從x移到z
        //******************************打印步驟需要，非執(zhí)行過(guò)程*********************
        printf("move %c from %c to %c\n",elem,*(x->This->base),*(z->This->base));
        x->risePrint(x);
        y->risePrint(y);
        z->risePrint(z);
        printf("\n");
        //***************************************************************************
    }else{
        hanoi(n-1,x,z,y);//將x上編號(hào)為1至n-1的圓盤移到y(tǒng)，z做輔助塔
        x->pop(x,&elem);
        z->push(z,&elem);//將編號(hào)為n的圓盤從x移到z
        //******************************打印步驟需要，非執(zhí)行過(guò)程*********************
        printf("move %c from %c to %c\n",elem,*(x->This->base),*(z->This->base));
        x->risePrint(x);
        y->risePrint(y);
        z->risePrint(z);
        printf("\n");
        //***************************************************************************
        hanoi(n-1,y,x,z);//將y上編號(hào)為1至n-1的圓盤移到z，x做輔助塔
    }
}

int main(void)
{
    int i;
    char elem;
    LinearListStack *x = InitLinearListStack();
    LinearListStack *y = InitLinearListStack();
    LinearListStack *z = InitLinearListStack();
    elem = 'x';
    x->push(x,&elem);
    elem = ':';
    x->push(x,&elem);
    elem = 'y';
    y->push(y,&elem);
    elem = ':';
    y->push(y,&elem);
    elem = 'z';
    z->push(z,&elem);
    elem = ':';
    z->push(z,&elem);
    for(i=9;i>0;i--){
        elem = i+0x30;
        x->push(x,&elem);
    }
    hanoi(9,x,y,z);
    DestroyLinearListStack(x);
    DestroyLinearListStack(y);
    DestroyLinearListStack(z);
    return 0;
}

編譯：

gcc LinearListStack.c LinearListStack.h TowerOfHanoi.c -o TowerOfHanoi

運(yùn)行TowerOfHanoi：

move 1 from x to z
x:98765432
y:
z:1

move 2 from x to y
x:9876543
z:1
y:2

move 1 from z to y
z:
x:9876543
y:21

move 3 from x to z
x:987654
y:21
z:3

move 1 from y to x
y:2
z:3
x:9876541

move 2 from y to z
y:
x:9876541
z:32

move 1 from x to z
x:987654
y:
z:321

move 4 from x to y
x:98765
z:321
y:4

move 1 from z to y
z:32
x:98765
y:41

move 2 from z to x
z:3
y:41
x:987652

move 1 from y to x
y:4
z:3
x:9876521

move 3 from z to y
z:
x:9876521
y:43

move 1 from x to z
x:987652
y:43
z:1

move 2 from x to y
x:98765
z:1
y:432

move 1 from z to y
z:
x:98765
y:4321

move 5 from x to z
x:9876
y:4321
z:5

move 1 from y to x
y:432
z:5
x:98761

move 2 from y to z
y:43
x:98761
z:52

move 1 from x to z
x:9876
y:43
z:521

move 3 from y to x
y:4
z:521
x:98763

move 1 from z to y
z:52
x:98763
y:41

move 2 from z to x
z:5
y:41
x:987632

move 1 from y to x
y:4
z:5
x:9876321

move 4 from y to z
y:
x:9876321
z:54

move 1 from x to z
x:987632
y:
z:541

move 2 from x to y
x:98763
z:541
y:2

move 1 from z to y
z:54
x:98763
y:21

move 3 from x to z
x:9876
y:21
z:543

move 1 from y to x
y:2
z:543
x:98761

move 2 from y to z
y:
x:98761
z:5432

move 1 from x to z
x:9876
y:
z:54321

move 6 from x to y
x:987
z:54321
y:6

move 1 from z to y
z:5432
x:987
y:61

move 2 from z to x
z:543
y:61
x:9872

move 1 from y to x
y:6
z:543
x:98721

move 3 from z to y
z:54
x:98721
y:63

move 1 from x to z
x:9872
y:63
z:541

move 2 from x to y
x:987
z:541
y:632

move 1 from z to y
z:54
x:987
y:6321

move 4 from z to x
z:5
y:6321
x:9874

move 1 from y to x
y:632
z:5
x:98741

move 2 from y to z
y:63
x:98741
z:52

move 1 from x to z
x:9874
y:63
z:521

move 3 from y to x
y:6
z:521
x:98743

move 1 from z to y
z:52
x:98743
y:61

move 2 from z to x
z:5
y:61
x:987432

move 1 from y to x
y:6
z:5
x:9874321

move 5 from z to y
z:
x:9874321
y:65

move 1 from x to z
x:987432
y:65
z:1

move 2 from x to y
x:98743
z:1
y:652

move 1 from z to y
z:
x:98743
y:6521

move 3 from x to z
x:9874
y:6521
z:3

move 1 from y to x
y:652
z:3
x:98741

move 2 from y to z
y:65
x:98741
z:32

move 1 from x to z
x:9874
y:65
z:321

move 4 from x to y
x:987
z:321
y:654

move 1 from z to y
z:32
x:987
y:6541

move 2 from z to x
z:3
y:6541
x:9872

move 1 from y to x
y:654
z:3
x:98721

move 3 from z to y
z:
x:98721
y:6543

move 1 from x to z
x:9872
y:6543
z:1

move 2 from x to y
x:987
z:1
y:65432

move 1 from z to y
z:
x:987
y:654321

move 7 from x to z
x:98
y:654321
z:7

move 1 from y to x
y:65432
z:7
x:981

move 2 from y to z
y:6543
x:981
z:72

move 1 from x to z
x:98
y:6543
z:721

move 3 from y to x
y:654
z:721
x:983

move 1 from z to y
z:72
x:983
y:6541

move 2 from z to x
z:7
y:6541
x:9832

move 1 from y to x
y:654
z:7
x:98321

move 4 from y to z
y:65
x:98321
z:74

move 1 from x to z
x:9832
y:65
z:741

move 2 from x to y
x:983
z:741
y:652

move 1 from z to y
z:74
x:983
y:6521

move 3 from x to z
x:98
y:6521
z:743

move 1 from y to x
y:652
z:743
x:981

move 2 from y to z
y:65
x:981
z:7432

move 1 from x to z
x:98
y:65
z:74321

move 5 from y to x
y:6
z:74321
x:985

move 1 from z to y
z:7432
x:985
y:61

move 2 from z to x
z:743
y:61
x:9852

move 1 from y to x
y:6
z:743
x:98521

move 3 from z to y
z:74
x:98521
y:63

move 1 from x to z
x:9852
y:63
z:741

move 2 from x to y
x:985
z:741
y:632

move 1 from z to y
z:74
x:985
y:6321

move 4 from z to x
z:7
y:6321
x:9854

move 1 from y to x
y:632
z:7
x:98541

move 2 from y to z
y:63
x:98541
z:72

move 1 from x to z
x:9854
y:63
z:721

move 3 from y to x
y:6
z:721
x:98543

move 1 from z to y
z:72
x:98543
y:61

move 2 from z to x
z:7
y:61
x:985432

move 1 from y to x
y:6
z:7
x:9854321

move 6 from y to z
y:
x:9854321
z:76

move 1 from x to z
x:985432
y:
z:761

move 2 from x to y
x:98543
z:761
y:2

move 1 from z to y
z:76
x:98543
y:21

move 3 from x to z
x:9854
y:21
z:763

move 1 from y to x
y:2
z:763
x:98541

move 2 from y to z
y:
x:98541
z:7632

move 1 from x to z
x:9854
y:
z:76321

move 4 from x to y
x:985
z:76321
y:4

move 1 from z to y
z:7632
x:985
y:41

move 2 from z to x
z:763
y:41
x:9852

move 1 from y to x
y:4
z:763
x:98521

move 3 from z to y
z:76
x:98521
y:43

move 1 from x to z
x:9852
y:43
z:761

move 2 from x to y
x:985
z:761
y:432

move 1 from z to y
z:76
x:985
y:4321

move 5 from x to z
x:98
y:4321
z:765

move 1 from y to x
y:432
z:765
x:981

move 2 from y to z
y:43
x:981
z:7652

move 1 from x to z
x:98
y:43
z:76521

move 3 from y to x
y:4
z:76521
x:983

move 1 from z to y
z:7652
x:983
y:41

move 2 from z to x
z:765
y:41
x:9832

move 1 from y to x
y:4
z:765
x:98321

move 4 from y to z
y:
x:98321
z:7654

move 1 from x to z
x:9832
y:
z:76541

move 2 from x to y
x:983
z:76541
y:2

move 1 from z to y
z:7654
x:983
y:21

move 3 from x to z
x:98
y:21
z:76543

move 1 from y to x
y:2
z:76543
x:981

move 2 from y to z
y:
x:981
z:765432

move 1 from x to z
x:98
y:
z:7654321

move 8 from x to y
x:9
z:7654321
y:8

move 1 from z to y
z:765432
x:9
y:81

move 2 from z to x
z:76543
y:81
x:92

move 1 from y to x
y:8
z:76543
x:921

move 3 from z to y
z:7654
x:921
y:83

move 1 from x to z
x:92
y:83
z:76541

move 2 from x to y
x:9
z:76541
y:832

move 1 from z to y
z:7654
x:9
y:8321

move 4 from z to x
z:765
y:8321
x:94

move 1 from y to x
y:832
z:765
x:941

move 2 from y to z
y:83
x:941
z:7652

move 1 from x to z
x:94
y:83
z:76521

move 3 from y to x
y:8
z:76521
x:943

move 1 from z to y
z:7652
x:943
y:81

move 2 from z to x
z:765
y:81
x:9432

move 1 from y to x
y:8
z:765
x:94321

move 5 from z to y
z:76
x:94321
y:85

move 1 from x to z
x:9432
y:85
z:761

move 2 from x to y
x:943
z:761
y:852

move 1 from z to y
z:76
x:943
y:8521

move 3 from x to z
x:94
y:8521
z:763

move 1 from y to x
y:852
z:763
x:941

move 2 from y to z
y:85
x:941
z:7632

move 1 from x to z
x:94
y:85
z:76321

move 4 from x to y
x:9
z:76321
y:854

move 1 from z to y
z:7632
x:9
y:8541

move 2 from z to x
z:763
y:8541
x:92

move 1 from y to x
y:854
z:763
x:921

move 3 from z to y
z:76
x:921
y:8543

move 1 from x to z
x:92
y:8543
z:761

move 2 from x to y
x:9
z:761
y:85432

move 1 from z to y
z:76
x:9
y:854321

move 6 from z to x
z:7
y:854321
x:96

move 1 from y to x
y:85432
z:7
x:961

move 2 from y to z
y:8543
x:961
z:72

move 1 from x to z
x:96
y:8543
z:721

move 3 from y to x
y:854
z:721
x:963

move 1 from z to y
z:72
x:963
y:8541

move 2 from z to x
z:7
y:8541
x:9632

move 1 from y to x
y:854
z:7
x:96321

move 4 from y to z
y:85
x:96321
z:74

move 1 from x to z
x:9632
y:85
z:741

move 2 from x to y
x:963
z:741
y:852

move 1 from z to y
z:74
x:963
y:8521

move 3 from x to z
x:96
y:8521
z:743

move 1 from y to x
y:852
z:743
x:961

move 2 from y to z
y:85
x:961
z:7432

move 1 from x to z
x:96
y:85
z:74321

move 5 from y to x
y:8
z:74321
x:965

move 1 from z to y
z:7432
x:965
y:81

move 2 from z to x
z:743
y:81
x:9652

move 1 from y to x
y:8
z:743
x:96521

move 3 from z to y
z:74
x:96521
y:83

move 1 from x to z
x:9652
y:83
z:741

move 2 from x to y
x:965
z:741
y:832

move 1 from z to y
z:74
x:965
y:8321

move 4 from z to x
z:7
y:8321
x:9654

move 1 from y to x
y:832
z:7
x:96541

move 2 from y to z
y:83
x:96541
z:72

move 1 from x to z
x:9654
y:83
z:721

move 3 from y to x
y:8
z:721
x:96543

move 1 from z to y
z:72
x:96543
y:81

move 2 from z to x
z:7
y:81
x:965432

move 1 from y to x
y:8
z:7
x:9654321

move 7 from z to y
z:
x:9654321
y:87

move 1 from x to z
x:965432
y:87
z:1

move 2 from x to y
x:96543
z:1
y:872

move 1 from z to y
z:
x:96543
y:8721

move 3 from x to z
x:9654
y:8721
z:3

move 1 from y to x
y:872
z:3
x:96541

move 2 from y to z
y:87
x:96541
z:32

move 1 from x to z
x:9654
y:87
z:321

move 4 from x to y
x:965
z:321
y:874

move 1 from z to y
z:32
x:965
y:8741

move 2 from z to x
z:3
y:8741
x:9652

move 1 from y to x
y:874
z:3
x:96521

move 3 from z to y
z:
x:96521
y:8743

move 1 from x to z
x:9652
y:8743
z:1

move 2 from x to y
x:965
z:1
y:87432

move 1 from z to y
z:
x:965
y:874321

move 5 from x to z
x:96
y:874321
z:5

move 1 from y to x
y:87432
z:5
x:961

move 2 from y to z
y:8743
x:961
z:52

move 1 from x to z
x:96
y:8743
z:521

move 3 from y to x
y:874
z:521
x:963

move 1 from z to y
z:52
x:963
y:8741

move 2 from z to x
z:5
y:8741
x:9632

move 1 from y to x
y:874
z:5
x:96321

move 4 from y to z
y:87
x:96321
z:54

move 1 from x to z
x:9632
y:87
z:541

move 2 from x to y
x:963
z:541
y:872

move 1 from z to y
z:54
x:963
y:8721

move 3 from x to z
x:96
y:8721
z:543

move 1 from y to x
y:872
z:543
x:961

move 2 from y to z
y:87
x:961
z:5432

move 1 from x to z
x:96
y:87
z:54321

move 6 from x to y
x:9
z:54321
y:876

move 1 from z to y
z:5432
x:9
y:8761

move 2 from z to x
z:543
y:8761
x:92

move 1 from y to x
y:876
z:543
x:921

move 3 from z to y
z:54
x:921
y:8763

move 1 from x to z
x:92
y:8763
z:541

move 2 from x to y
x:9
z:541
y:87632

move 1 from z to y
z:54
x:9
y:876321

move 4 from z to x
z:5
y:876321
x:94

move 1 from y to x
y:87632
z:5
x:941

move 2 from y to z
y:8763
x:941
z:52

move 1 from x to z
x:94
y:8763
z:521

move 3 from y to x
y:876
z:521
x:943

move 1 from z to y
z:52
x:943
y:8761

move 2 from z to x
z:5
y:8761
x:9432

move 1 from y to x
y:876
z:5
x:94321

move 5 from z to y
z:
x:94321
y:8765

move 1 from x to z
x:9432
y:8765
z:1

move 2 from x to y
x:943
z:1
y:87652

move 1 from z to y
z:
x:943
y:876521

move 3 from x to z
x:94
y:876521
z:3

move 1 from y to x
y:87652
z:3
x:941

move 2 from y to z
y:8765
x:941
z:32

move 1 from x to z
x:94
y:8765
z:321

move 4 from x to y
x:9
z:321
y:87654

move 1 from z to y
z:32
x:9
y:876541

move 2 from z to x
z:3
y:876541
x:92

move 1 from y to x
y:87654
z:3
x:921

move 3 from z to y
z:
x:921
y:876543

move 1 from x to z
x:92
y:876543
z:1

move 2 from x to y
x:9
z:1
y:8765432

move 1 from z to y
z:
x:9
y:87654321

move 9 from x to z
x:
y:87654321
z:9

move 1 from y to x
y:8765432
z:9
x:1

move 2 from y to z
y:876543
x:1
z:92

move 1 from x to z
x:
y:876543
z:921

move 3 from y to x
y:87654
z:921
x:3

move 1 from z to y
z:92
x:3
y:876541

move 2 from z to x
z:9
y:876541
x:32

move 1 from y to x
y:87654
z:9
x:321

move 4 from y to z
y:8765
x:321
z:94

move 1 from x to z
x:32
y:8765
z:941

move 2 from x to y
x:3
z:941
y:87652

move 1 from z to y
z:94
x:3
y:876521

move 3 from x to z
x:
y:876521
z:943

move 1 from y to x
y:87652
z:943
x:1

move 2 from y to z
y:8765
x:1
z:9432

move 1 from x to z
x:
y:8765
z:94321

move 5 from y to x
y:876
z:94321
x:5

move 1 from z to y
z:9432
x:5
y:8761

move 2 from z to x
z:943
y:8761
x:52

move 1 from y to x
y:876
z:943
x:521

move 3 from z to y
z:94
x:521
y:8763

move 1 from x to z
x:52
y:8763
z:941

move 2 from x to y
x:5
z:941
y:87632

move 1 from z to y
z:94
x:5
y:876321

move 4 from z to x
z:9
y:876321
x:54

move 1 from y to x
y:87632
z:9
x:541

move 2 from y to z
y:8763
x:541
z:92

move 1 from x to z
x:54
y:8763
z:921

move 3 from y to x
y:876
z:921
x:543

move 1 from z to y
z:92
x:543
y:8761

move 2 from z to x
z:9
y:8761
x:5432

move 1 from y to x
y:876
z:9
x:54321

move 6 from y to z
y:87
x:54321
z:96

move 1 from x to z
x:5432
y:87
z:961

move 2 from x to y
x:543
z:961
y:872

move 1 from z to y
z:96
x:543
y:8721

move 3 from x to z
x:54
y:8721
z:963

move 1 from y to x
y:872
z:963
x:541

move 2 from y to z
y:87
x:541
z:9632

move 1 from x to z
x:54
y:87
z:96321

move 4 from x to y
x:5
z:96321
y:874

move 1 from z to y
z:9632
x:5
y:8741

move 2 from z to x
z:963
y:8741
x:52

move 1 from y to x
y:874
z:963
x:521

move 3 from z to y
z:96
x:521
y:8743

move 1 from x to z
x:52
y:8743
z:961

move 2 from x to y
x:5
z:961
y:87432

move 1 from z to y
z:96
x:5
y:874321

move 5 from x to z
x:
y:874321
z:965

move 1 from y to x
y:87432
z:965
x:1

move 2 from y to z
y:8743
x:1
z:9652

move 1 from x to z
x:
y:8743
z:96521

move 3 from y to x
y:874
z:96521
x:3

move 1 from z to y
z:9652
x:3
y:8741

move 2 from z to x
z:965
y:8741
x:32

move 1 from y to x
y:874
z:965
x:321

move 4 from y to z
y:87
x:321
z:9654

move 1 from x to z
x:32
y:87
z:96541

move 2 from x to y
x:3
z:96541
y:872

move 1 from z to y
z:9654
x:3
y:8721

move 3 from x to z
x:
y:8721
z:96543

move 1 from y to x
y:872
z:96543
x:1

move 2 from y to z
y:87
x:1
z:965432

move 1 from x to z
x:
y:87
z:9654321

move 7 from y to x
y:8
z:9654321
x:7

move 1 from z to y
z:965432
x:7
y:81

move 2 from z to x
z:96543
y:81
x:72

move 1 from y to x
y:8
z:96543
x:721

move 3 from z to y
z:9654
x:721
y:83

move 1 from x to z
x:72
y:83
z:96541

move 2 from x to y
x:7
z:96541
y:832

move 1 from z to y
z:9654
x:7
y:8321

move 4 from z to x
z:965
y:8321
x:74

move 1 from y to x
y:832
z:965
x:741

move 2 from y to z
y:83
x:741
z:9652

move 1 from x to z
x:74
y:83
z:96521

move 3 from y to x
y:8
z:96521
x:743

move 1 from z to y
z:9652
x:743
y:81

move 2 from z to x
z:965
y:81
x:7432

move 1 from y to x
y:8
z:965
x:74321

move 5 from z to y
z:96
x:74321
y:85

move 1 from x to z
x:7432
y:85
z:961

move 2 from x to y
x:743
z:961
y:852

move 1 from z to y
z:96
x:743
y:8521

move 3 from x to z
x:74
y:8521
z:963

move 1 from y to x
y:852
z:963
x:741

move 2 from y to z
y:85
x:741
z:9632

move 1 from x to z
x:74
y:85
z:96321

move 4 from x to y
x:7
z:96321
y:854

move 1 from z to y
z:9632
x:7
y:8541

move 2 from z to x
z:963
y:8541
x:72

move 1 from y to x
y:854
z:963
x:721

move 3 from z to y
z:96
x:721
y:8543

move 1 from x to z
x:72
y:8543
z:961

move 2 from x to y
x:7
z:961
y:85432

move 1 from z to y
z:96
x:7
y:854321

move 6 from z to x
z:9
y:854321
x:76

move 1 from y to x
y:85432
z:9
x:761

move 2 from y to z
y:8543
x:761
z:92

move 1 from x to z
x:76
y:8543
z:921

move 3 from y to x
y:854
z:921
x:763

move 1 from z to y
z:92
x:763
y:8541

move 2 from z to x
z:9
y:8541
x:7632

move 1 from y to x
y:854
z:9
x:76321

move 4 from y to z
y:85
x:76321
z:94

move 1 from x to z
x:7632
y:85
z:941

move 2 from x to y
x:763
z:941
y:852

move 1 from z to y
z:94
x:763
y:8521

move 3 from x to z
x:76
y:8521
z:943

move 1 from y to x
y:852
z:943
x:761

move 2 from y to z
y:85
x:761
z:9432

move 1 from x to z
x:76
y:85
z:94321

move 5 from y to x
y:8
z:94321
x:765

move 1 from z to y
z:9432
x:765
y:81

move 2 from z to x
z:943
y:81
x:7652

move 1 from y to x
y:8
z:943
x:76521

move 3 from z to y
z:94
x:76521
y:83

move 1 from x to z
x:7652
y:83
z:941

move 2 from x to y
x:765
z:941
y:832

move 1 from z to y
z:94
x:765
y:8321

move 4 from z to x
z:9
y:8321
x:7654

move 1 from y to x
y:832
z:9
x:76541

move 2 from y to z
y:83
x:76541
z:92

move 1 from x to z
x:7654
y:83
z:921

move 3 from y to x
y:8
z:921
x:76543

move 1 from z to y
z:92
x:76543
y:81

move 2 from z to x
z:9
y:81
x:765432

move 1 from y to x
y:8
z:9
x:7654321

move 8 from y to z
y:
x:7654321
z:98

move 1 from x to z
x:765432
y:
z:981

move 2 from x to y
x:76543
z:981
y:2

move 1 from z to y
z:98
x:76543
y:21

move 3 from x to z
x:7654
y:21
z:983

move 1 from y to x
y:2
z:983
x:76541

move 2 from y to z
y:
x:76541
z:9832

move 1 from x to z
x:7654
y:
z:98321

move 4 from x to y
x:765
z:98321
y:4

move 1 from z to y
z:9832
x:765
y:41

move 2 from z to x
z:983
y:41
x:7652

move 1 from y to x
y:4
z:983
x:76521

move 3 from z to y
z:98
x:76521
y:43

move 1 from x to z
x:7652
y:43
z:981

move 2 from x to y
x:765
z:981
y:432

move 1 from z to y
z:98
x:765
y:4321

move 5 from x to z
x:76
y:4321
z:985

move 1 from y to x
y:432
z:985
x:761

move 2 from y to z
y:43
x:761
z:9852

move 1 from x to z
x:76
y:43
z:98521

move 3 from y to x
y:4
z:98521
x:763

move 1 from z to y
z:9852
x:763
y:41

move 2 from z to x
z:985
y:41
x:7632

move 1 from y to x
y:4
z:985
x:76321

move 4 from y to z
y:
x:76321
z:9854

move 1 from x to z
x:7632
y:
z:98541

move 2 from x to y
x:763
z:98541
y:2

move 1 from z to y
z:9854
x:763
y:21

move 3 from x to z
x:76
y:21
z:98543

move 1 from y to x
y:2
z:98543
x:761

move 2 from y to z
y:
x:761
z:985432

move 1 from x to z
x:76
y:
z:9854321

move 6 from x to y
x:7
z:9854321
y:6

move 1 from z to y
z:985432
x:7
y:61

move 2 from z to x
z:98543
y:61
x:72

move 1 from y to x
y:6
z:98543
x:721

move 3 from z to y
z:9854
x:721
y:63

move 1 from x to z
x:72
y:63
z:98541

move 2 from x to y
x:7
z:98541
y:632

move 1 from z to y
z:9854
x:7
y:6321

move 4 from z to x
z:985
y:6321
x:74

move 1 from y to x
y:632
z:985
x:741

move 2 from y to z
y:63
x:741
z:9852

move 1 from x to z
x:74
y:63
z:98521

move 3 from y to x
y:6
z:98521
x:743

move 1 from z to y
z:9852
x:743
y:61

move 2 from z to x
z:985
y:61
x:7432

move 1 from y to x
y:6
z:985
x:74321

move 5 from z to y
z:98
x:74321
y:65

move 1 from x to z
x:7432
y:65
z:981

move 2 from x to y
x:743
z:981
y:652

move 1 from z to y
z:98
x:743
y:6521

move 3 from x to z
x:74
y:6521
z:983

move 1 from y to x
y:652
z:983
x:741

move 2 from y to z
y:65
x:741
z:9832

move 1 from x to z
x:74
y:65
z:98321

move 4 from x to y
x:7
z:98321
y:654

move 1 from z to y
z:9832
x:7
y:6541

move 2 from z to x
z:983
y:6541
x:72

move 1 from y to x
y:654
z:983
x:721

move 3 from z to y
z:98
x:721
y:6543

move 1 from x to z
x:72
y:6543
z:981

move 2 from x to y
x:7
z:981
y:65432

move 1 from z to y
z:98
x:7
y:654321

move 7 from x to z
x:
y:654321
z:987

move 1 from y to x
y:65432
z:987
x:1

move 2 from y to z
y:6543
x:1
z:9872

move 1 from x to z
x:
y:6543
z:98721

move 3 from y to x
y:654
z:98721
x:3

move 1 from z to y
z:9872
x:3
y:6541

move 2 from z to x
z:987
y:6541
x:32

move 1 from y to x
y:654
z:987
x:321

move 4 from y to z
y:65
x:321
z:9874

move 1 from x to z
x:32
y:65
z:98741

move 2 from x to y
x:3
z:98741
y:652

move 1 from z to y
z:9874
x:3
y:6521

move 3 from x to z
x:
y:6521
z:98743

move 1 from y to x
y:652
z:98743
x:1

move 2 from y to z
y:65
x:1
z:987432

move 1 from x to z
x:
y:65
z:9874321

move 5 from y to x
y:6
z:9874321
x:5

move 1 from z to y
z:987432
x:5
y:61

move 2 from z to x
z:98743
y:61
x:52

move 1 from y to x
y:6
z:98743
x:521

move 3 from z to y
z:9874
x:521
y:63

move 1 from x to z
x:52
y:63
z:98741

move 2 from x to y
x:5
z:98741
y:632

move 1 from z to y
z:9874
x:5
y:6321

move 4 from z to x
z:987
y:6321
x:54

move 1 from y to x
y:632
z:987
x:541

move 2 from y to z
y:63
x:541
z:9872

move 1 from x to z
x:54
y:63
z:98721

move 3 from y to x
y:6
z:98721
x:543

move 1 from z to y
z:9872
x:543
y:61

move 2 from z to x
z:987
y:61
x:5432

move 1 from y to x
y:6
z:987
x:54321

move 6 from y to z
y:
x:54321
z:9876

move 1 from x to z
x:5432
y:
z:98761

move 2 from x to y
x:543
z:98761
y:2

move 1 from z to y
z:9876
x:543
y:21

move 3 from x to z
x:54
y:21
z:98763

move 1 from y to x
y:2
z:98763
x:541

move 2 from y to z
y:
x:541
z:987632

move 1 from x to z
x:54
y:
z:9876321

move 4 from x to y
x:5
z:9876321
y:4

move 1 from z to y
z:987632
x:5
y:41

move 2 from z to x
z:98763
y:41
x:52

move 1 from y to x
y:4
z:98763
x:521

move 3 from z to y
z:9876
x:521
y:43

move 1 from x to z
x:52
y:43
z:98761

move 2 from x to y
x:5
z:98761
y:432

move 1 from z to y
z:9876
x:5
y:4321

move 5 from x to z
x:
y:4321
z:98765

move 1 from y to x
y:432
z:98765
x:1

move 2 from y to z
y:43
x:1
z:987652

move 1 from x to z
x:
y:43
z:9876521

move 3 from y to x
y:4
z:9876521
x:3

move 1 from z to y
z:987652
x:3
y:41

move 2 from z to x
z:98765
y:41
x:32

move 1 from y to x
y:4
z:98765
x:321

move 4 from y to z
y:
x:321
z:987654

move 1 from x to z
x:32
y:
z:9876541

move 2 from x to y
x:3
z:9876541
y:2

move 1 from z to y
z:987654
x:3
y:21

move 3 from x to z
x:
y:21
z:9876543

move 1 from y to x
y:2
z:9876543
x:1

move 2 from y to z
y:
x:1
z:98765432

move 1 from x to z
x:
y:
z:987654321

顯然這是一個(gè)遞歸函數(shù)，在函數(shù)的執(zhí)行函數(shù)中，需多次進(jìn)行自我調(diào)用。那么，這個(gè)遞歸函數(shù)是如何執(zhí)行的？

先看任意兩個(gè)函數(shù)之間進(jìn)行調(diào)用的情形：
與匯編程序中主程序和子程序之間的鏈接及信息交換相類似，在高級(jí)語(yǔ)言編制的程序中，調(diào)用函數(shù)和被調(diào)用函數(shù)之間的鏈接及信息交換需通過(guò)棧來(lái)執(zhí)行。

通常，當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行被調(diào)用函數(shù)之前，系統(tǒng)需先完成3件事：
1.將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存。
2.為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)。
3.將控制轉(zhuǎn)移到被調(diào)函數(shù)入口。

而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，系統(tǒng)也完成3件事：
1.保存被調(diào)函數(shù)的計(jì)算結(jié)果。
2.釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)。
3.依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。

當(dāng)有多個(gè)函數(shù)構(gòu)成嵌套調(diào)用時(shí)，按照“后調(diào)用先返回”的原則，上述函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過(guò)"棧"來(lái)實(shí)現(xiàn)，即系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需的數(shù)據(jù)空間安排在一個(gè)棧中，每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，就為它在棧頂分配一個(gè)存儲(chǔ)區(qū)，每當(dāng)從一個(gè)函數(shù)退出時(shí)，就釋放它的存儲(chǔ)區(qū)，則當(dāng)前正運(yùn)行的函數(shù)的數(shù)據(jù)區(qū)必在棧頂。

以下代碼為例：

int first(int s, int t);
int second(int d);

int main(){
    int m,n;
    ...
    first(m,n);
    1:...
}

int first(int s, int t){
    int i;
    ...
    second(i);
    2:...
}

int second(int d){
    int x,y;
    ...
}

主函數(shù)main中調(diào)用了函數(shù)first，而在函數(shù)first中又調(diào)用了函數(shù)second，
下圖展示了當(dāng)前正在執(zhí)行函數(shù)second中某個(gè)語(yǔ)句時(shí)棧的狀態(tài)，圖中1，2表示返回地址：

image.png

下圖展示了從函數(shù)second退出之后正執(zhí)行函數(shù)first中某個(gè)語(yǔ)句時(shí)棧的狀態(tài)，圖中1表示返回地址：

image.png

一個(gè)遞歸函數(shù)的運(yùn)行過(guò)程類似于多個(gè)函數(shù)的嵌套調(diào)用，只是調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)，因此，和每次調(diào)用相關(guān)的一個(gè)重要概念是遞歸函數(shù)運(yùn)行的“層次”：
假設(shè)調(diào)用該遞歸函數(shù)的主函數(shù)為第0層，
則從主函數(shù)調(diào)用遞歸函數(shù)為進(jìn)入第1層；
從第i層遞歸調(diào)用本函數(shù)為進(jìn)入“下一層”，即第i+1層。
反之，退出第i層遞歸應(yīng)返回至上一層。

為了保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)需設(shè)立一個(gè)"遞歸工作棧"作為整個(gè)遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)存儲(chǔ)區(qū)。
每一層遞歸所需信息構(gòu)成一個(gè)“工作記錄”，其中包括所有的實(shí)在參數(shù)、所有的局部變量以及上一層返回的地址。
每進(jìn)入一層遞歸，就產(chǎn)生一個(gè)新的工作記錄壓入棧頂。
每退出一層遞歸，就從棧頂彈出一個(gè)工作記錄，則當(dāng)前執(zhí)行層的工作記錄必是遞歸工作棧棧頂?shù)墓ぷ饔涗?，稱這個(gè)記錄為“活動(dòng)記錄”，并稱指示活動(dòng)記錄的棧頂指針為“當(dāng)前環(huán)境指針”。

由于遞歸函數(shù)結(jié)構(gòu)清晰，程序易讀，而且它的正確性容易得到證明，因此，利用允許遞歸調(diào)用的語(yǔ)言進(jìn)行程序設(shè)計(jì)時(shí)，給用戶編制程序帶來(lái)很大方便。因?yàn)閷?duì)這樣一類遞歸問(wèn)題編程時(shí)，不需要用戶自己而由系統(tǒng)來(lái)管理遞歸工作棧。

理解遞歸

在初學(xué)遞歸的時(shí)候, 看到一個(gè)遞歸實(shí)現(xiàn), 我們總是難免陷入不停的回溯驗(yàn)證之中, 因?yàn)榛厮菥拖穹催^(guò)來(lái)思考迭代, 這是我們習(xí)慣的思維方式, 但是實(shí)際上遞歸不需要這樣來(lái)驗(yàn)證。
比如, 階乘的計(jì)算：
階乘的定義: “一個(gè)正整數(shù)的階乘（英語(yǔ)：factorial）是所有小于或等于該數(shù)的正整數(shù)的積，并且0的階乘為1?！?br> 代碼實(shí)現(xiàn)：

int Fact(int n){
    if(n<=1){
        return 1;
    }else{
        return n * Fact(n - 1);
    }
}

我們?cè)趺磁袛噙@個(gè)階乘的遞歸計(jì)算是否是正確的呢?
回溯的思考方式是這么驗(yàn)證的, 比如當(dāng)n = 4時(shí), 那么Fact(4)等于4 *Fact(3), 而Fact(3)等于3 * Fact(2), Fact(2)等于2 * Fact(1), 等于2 * 1, 所以Fact(4)等于4 * 3 * 2 * 1. 這個(gè)結(jié)果正好等于階乘4的迭代定義。
用回溯的方式思考雖然可以驗(yàn)證當(dāng)n = 某個(gè)較小數(shù)值是否正確, 但是其實(shí)無(wú)益于理解。

Paul Graham提到一種驗(yàn)證方法：
當(dāng)n=0, 1的時(shí)候, 結(jié)果正確，
假設(shè)函數(shù)對(duì)于n是正確的, 函數(shù)對(duì)n+1結(jié)果也正確，
如果這兩點(diǎn)是成立的，我們知道這個(gè)函數(shù)對(duì)于所有可能的n都是正確的。
這種方法很像數(shù)學(xué)歸納法, 也是遞歸正確的思考方式。

如何找到一個(gè)適用遞歸算法的問(wèn)題

上面講了怎么理解遞歸是正確的, 同時(shí)可以看到在有遞歸算法描述后, 其實(shí)程序很容易寫, 那么最關(guān)鍵的問(wèn)題就是, 我們?cè)趺凑业揭粋€(gè)問(wèn)題的遞歸算法呢?

Paul Graham提到, 你只需要做兩件事情:
你必須要示范如何解決問(wèn)題的一般情況, 通過(guò)將問(wèn)題切分成有限小并更小的子問(wèn)題。
你必須要示范如何通過(guò)有限的步驟, 來(lái)解決最小的問(wèn)題(基本用例)。
如果這兩件事完成了, 那問(wèn)題就解決了。因?yàn)檫f歸每次都將問(wèn)題變得更小, 而一個(gè)有限的問(wèn)題終究會(huì)被解決的, 而最小的問(wèn)題僅需幾個(gè)有限的步驟就能解決。

在什么情況下用遞歸

遞歸并不一定適用所有情況, 很多情況用迭代遠(yuǎn)遠(yuǎn)比用遞歸好了解；其次, 相對(duì)來(lái)說(shuō), 遞歸的效率往往要低于迭代的實(shí)現(xiàn)，同時(shí), 內(nèi)存消耗也會(huì)更大。

以上面的階乘算法為例，如果n = 100，很顯然這段程序需要遞歸地調(diào)用自身100次。這樣調(diào)用深度至少就到了100。棧的大小是有限的，當(dāng)n變的更大時(shí)，有朝一日總會(huì)使得棧溢出，從而程序崩潰。除此之外，每次函數(shù)調(diào)用的開(kāi)銷會(huì)導(dǎo)致程序變慢。所以說(shuō)這段程序十分不好。

什么是好的遞歸：如果遞歸能夠?qū)?wèn)題的規(guī)?？s小，那就是好的遞歸。

怎樣才算是規(guī)模縮小了呢。舉個(gè)例子，比如要在一個(gè)有序數(shù)組中查找一個(gè)數(shù)，最簡(jiǎn)單直觀的算法就是從頭到尾遍歷一遍數(shù)組，這樣一定可以找到那個(gè)數(shù)。如果數(shù)組的大小是N，那么我們最壞情況下需要比較N次，所以這個(gè)算法的復(fù)雜度記為O(N)。有一個(gè)大名鼎鼎的算法叫二分法，它的表達(dá)也很簡(jiǎn)單，由于數(shù)組是有序的，那么找的時(shí)候就從數(shù)組的中間開(kāi)始找，如果要找的數(shù)比中間的數(shù)大，那么接著查找數(shù)組的后半部分(如果是升序的話)，以此類推，知道最后找到我們要找的數(shù)。稍微思考一下可以發(fā)現(xiàn)，如果數(shù)組的大小是N，那么最壞情況下我們需要比較logN次(計(jì)算機(jī)世界中l(wèi)og的底幾乎總是2)，所以這個(gè)算法的復(fù)雜度為O(logN)。

簡(jiǎn)單的分析一下二分法為什么會(huì)快。可以發(fā)現(xiàn)二分法在每次比較之后都幫我們排除了一半的錯(cuò)誤答案，接下去的一次只需要搜索剩下的一半，這就是說(shuō)問(wèn)題的規(guī)?？s小了一半。而在直觀的算法中，每次比較后最多排除了一個(gè)錯(cuò)誤的答案，問(wèn)題的規(guī)模幾乎沒(méi)有縮小(僅僅減少了1)。這樣的遞歸就稍微像樣點(diǎn)了。

重新看階乘的遞歸，每次遞歸后問(wèn)題并沒(méi)有本質(zhì)上的減小(僅僅減小1)，這和簡(jiǎn)單的循環(huán)沒(méi)有區(qū)別，但循環(huán)沒(méi)有函數(shù)調(diào)用的開(kāi)銷，也不會(huì)導(dǎo)致棧溢出。所以結(jié)論是如果僅僅用遞歸來(lái)達(dá)到循環(huán)的效果，那還是改用循環(huán)吧。

總結(jié)一下，遞歸的意義就在于將問(wèn)題的規(guī)模縮小，并且縮小后問(wèn)題并沒(méi)有發(fā)生變化(二分法中，縮小后依然是從數(shù)組中尋找某一個(gè)數(shù))，這樣就可以繼續(xù)調(diào)用自身來(lái)完成接下來(lái)的任務(wù)。我們不用寫很長(zhǎng)的程序，就能得到一個(gè)十分優(yōu)雅快速的實(shí)現(xiàn)。

如何寫遞歸

以二分查找算法為例子，首先給出函數(shù)原型，返回值是元素在數(shù)組中的位置，如果查找失敗返回-1。：

int binarySearch(int *array,int start,int end,int num_wanted)

1.基準(zhǔn)情況
基準(zhǔn)情況其實(shí)就是遞歸的終止條件。其實(shí)在實(shí)際中，這是十分容易確定的。例如在二分查找中，終止條件就是找到了我們想要的數(shù)或者搜索完了整個(gè)數(shù)組(查找失敗)。

    if(end < start){
        return -1;
    }else if(num_wanted == array[middle]){
        return middle;
    }

2.不斷演進(jìn)
演進(jìn)的過(guò)程就是我們思考的過(guò)程，二分查找中，就是繼續(xù)查找剩下的一半數(shù)組。

    if(num_wanted > array[middle]){
        index = binarySearch(array,middle + 1,end,num_wanted);
    }else{
        index = binarySearch(array,start,middle - 1,num_wanted);
    }

3.用人的思考方式設(shè)計(jì)
這條法則我認(rèn)為是非常重要的，它不會(huì)出現(xiàn)在編碼中，但卻是理解遞歸的一條捷徑。它的意思是說(shuō)，在一般的編程實(shí)踐中，我們通常需要用大腦模擬電腦執(zhí)行每一條語(yǔ)句，從而確定編碼的正確性，然而在遞歸編碼中這是不需要的。遞歸編碼的過(guò)程中，只需要知道前兩條法則就夠了。之后我們就會(huì)看到這條法則的如何工作的了。
4. 不要做重復(fù)的事情
在任何編碼中，這都是不應(yīng)該出現(xiàn)的事情，但是在遞歸中這更加可怕，可能由于一次多余的遞歸使得算法增加數(shù)級(jí)復(fù)雜度。

完整的二分法的程序：

int binarySearch(int *array,int start,int end,int num_wanted){
    int middle = (end - start)/2 + start; //1
    int index;
    if(end < start){
        return -1;
    }else if(num_wanted == array[middle]){
        return middle;
    }
    if(num_wanted > array[middle]){
        index = binarySearch(array,middle + 1,end,num_wanted); //2
    }else{
        index = binarySearch(array,start,middle - 1,num_wanted); //3
    }
    return index; //4
}

程序中除了1和4都已經(jīng)在前兩條法則的實(shí)現(xiàn)中了。
1不必多說(shuō)，4是一個(gè)比較關(guān)鍵的步驟，經(jīng)常容易被忘記。
這里就用到第3條法則，編寫的時(shí)候只要認(rèn)為2或者3一定會(huì)正確運(yùn)行，并且立刻返回，
不要考慮2和3內(nèi)部是如何運(yùn)行的，因?yàn)檫@就是你現(xiàn)在在編寫的。
這樣4該如何處理就是顯而易見(jiàn)的了，在這里只需要將找到的index返回就可以了。

第4條法則在這個(gè)例子里并沒(méi)有出現(xiàn)，我們可以看一下斐波那契數(shù)列的遞歸實(shí)現(xiàn)。

long int fib(int n){
    if(n <= 1){
        return 1;
    }else{
        return fib(n-1) + fib(n-2); // 1
    }
}

乍看之下，這段程序很精練，它也是一段正確的遞歸程序，有基準(zhǔn)條件、不斷推進(jìn)。但是如果仔細(xì)分析一下它的復(fù)雜度可以發(fā)現(xiàn)，如果我們?nèi)=N，那么每次fib調(diào)用會(huì)增加額外的2次fib調(diào)用(在1處)，即fib的運(yùn)行時(shí)間T(N) = T(N-1) + T(N-2)，可以得到其復(fù)雜度是O(2^N)，幾乎是可見(jiàn)的復(fù)雜度最大的程序了。

所以如果在一個(gè)遞歸程序中重復(fù)多次地調(diào)用自身，又不縮小問(wèn)題的規(guī)模，通常不是個(gè)好主意。

尾遞歸

到此其實(shí)你已經(jīng)可以寫出任何一個(gè)完整的遞歸程序了，雖然上面的例子比較簡(jiǎn)單，但是方法總是這樣的。

不過(guò)我們可以對(duì)遞歸程序再進(jìn)一步分析。二分查找的遞歸算法中我們注意到在遞歸調(diào)用之后僅僅是返回了其返回值，這樣的遞歸稱作尾遞歸。

盡管在編寫的時(shí)候不必考慮遞歸的調(diào)用順序，但真正運(yùn)行的時(shí)候，遞歸的函數(shù)調(diào)用過(guò)程可以分為遞和歸兩部分。
在遞歸調(diào)用之前的部分稱作遞，調(diào)用之后的部分稱作歸。

而尾遞歸在歸的過(guò)程中實(shí)際上不做任何事情，對(duì)于這種情況可以很方便的將這個(gè)遞歸程序轉(zhuǎn)化為非遞歸程序。

int binarySearch(int *array,int start,int end,int num_wanted){
    int middle;
search:
    middle = (end - start)/2 + start;
    if(end < start){
        return -1;
    }else if(num_wanted == array[middle]){
        return middle;
    }
    if(num_wanted > array[middle]){
        start = middle+1;
        end = end;
        goto search;
        //index = binary_search(array, middle+1, end, num_wanted);
    }else{
        start = start;
        end = middle-1;
        goto search;
        //index = binary_search(array, start, middle-1, num_wanted);
    }
}

上面就是去除遞歸后的二分查找的程序，我們只需要在程序開(kāi)頭處加上一個(gè)標(biāo)號(hào)，在原本遞歸調(diào)用處修改參數(shù)的值并goto到標(biāo)號(hào)就能完成這個(gè)工作。

事實(shí)上，如果你寫出了一個(gè)尾遞歸程序，在編譯的時(shí)候編譯器很可能就這樣幫你優(yōu)化了。當(dāng)然這樣的程序非常不符合我們的習(xí)慣，它實(shí)際上是將遞歸轉(zhuǎn)化為了循環(huán)。

循環(huán)還是應(yīng)當(dāng)使用while或者for實(shí)現(xiàn)，仔細(xì)地將上面這段程序改成while循環(huán)就成了這樣。

int binarySearch(int *array,int start,int end,int num_wanted){
    int middle = (end - start)/2 + start;
    while(end >= start && num_wanted != array[middle]){
        if(num_wanted > array[middle]){
            start = middle+1;
        }else{
            end = middle-1;
        }
        middle = (end - start)/2 + start;
    }
    if(end < start){
        return -1;
    }else{
        return middle;
    }
}

這樣就更加符合我們的習(xí)慣了，它比遞歸的版本速度略有提高，最重要的是不會(huì)導(dǎo)致棧溢出。

部分內(nèi)容摘自怎么寫一個(gè)遞歸程序