棧與遞歸的實(shí)現(xiàn)

棧與遞歸

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

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

Fact(n)=	1	若n=0
	n*Fact(n-1)	若n>0

2階Fibonacci數(shù)列：

Fib(n)=	0	若n=0
	1	若n=1
	Fib(n-1) + Fibz(n - 2)	其他情形

Ackerman函數(shù)：

Ack(m,n)=	n+1	若m=0
	Ack(m-1,1)	若n=0
	Ack(m-1,Ack(m,n-1))	其他情形

其二碧囊，有的數(shù)據(jù)結(jié)構(gòu)树灶，如二叉樹(shù)、廣義表等糯而，由于結(jié)構(gòu)本身固有的遞歸特性天通，則它們的操作可遞歸的描述；
其三熄驼，還有一類(lèi)問(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的圓盤(pán)⊙鲑鳎現(xiàn)要求將X軸上的n個(gè)圓盤(pán)移至塔座Z上并仍按同樣順序疊排照雁，圓盤(pán)移動(dòng)時(shí)必須遵循下列規(guī)則：
1.每次只能移動(dòng)一個(gè)圓盤(pán)
2.圓盤(pán)可以插在X 、Y答恶、Z中的任一塔座上
3.任何時(shí)刻都不能將一個(gè)較大的圓盤(pán)壓在較小的圓盤(pán)上饺蚊。

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

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

而如何將n-1個(gè)圓盤(pán)從一個(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的圓盤(pá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");
        //***************************************************************************
    }else{
        hanoi(n-1,x,z,y);//將x上編號(hào)為1至n-1的圓盤(pán)移到y(tǒng)囤攀，z做輔助塔
        x->pop(x,&elem);
        z->push(z,&elem);//將編號(hào)為n的圓盤(pá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的圓盤(pán)移到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)用的情形：
與匯編程序中主程序和子程序之間的鏈接及信息交換相類(lèi)似蝌蹂，在高級(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ò)程類(lèi)似于多個(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ù)墓ぷ饔涗洠Q(chēng)這個(gè)記錄為“活動(dòng)記錄”晤斩，并稱(chēng)指示活動(dòng)記錄的棧頂指針為“當(dāng)前環(huán)境指針”焕檬。

由于遞歸函數(shù)結(jié)構(gòu)清晰褥伴，程序易讀雀摘，而且它的正確性容易得到證明，因此畸写，利用允許遞歸調(diào)用的語(yǔ)言進(jìn)行程序設(shè)計(jì)時(shí)兔辅，給用戶(hù)編制程序帶來(lái)很大方便腊敲。因?yàn)閷?duì)這樣一類(lèi)遞歸問(wèn)題編程時(shí)，不需要用戶(hù)自己而由系統(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介时∶槐觯”
代碼實(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í)程序很容易寫(xiě), 那么最關(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)銷(xiāo)會(huì)導(dǎo)致程序變慢催式。所以說(shuō)這段程序十分不好。

什么是好的遞歸：如果遞歸能夠?qū)?wèn)題的規(guī)谋芄椋縮小荣月，那就是好的遞歸。

怎樣才算是規(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ù)組的后半部分(如果是升序的話(huà))，以此類(lèi)推番甩，知道最后找到我們要找的數(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ī)钠蚵Γ縮小了一半。而在直觀的算法中显歧，每次比較后最多排除了一個(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)銷(xiāo)瓶逃，也不會(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ù)靶病。我們不用寫(xiě)很長(zhǎng)的程序会通，就能得到一個(gè)十分優(yōu)雅快速的實(shí)現(xiàn)。

如何寫(xiě)遞歸

以二分查找算法為例子娄周，首先給出函數(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條法則组贺，編寫(xiě)的時(shí)候只要認(rèn)為2或者3一定會(huì)正確運(yùn)行，并且立刻返回祖娘，
不要考慮2和3內(nèi)部是如何運(yùn)行的失尖，因?yàn)檫@就是你現(xiàn)在在編寫(xiě)的。
這樣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)可以寫(xiě)出任何一個(gè)完整的遞歸程序了副渴，雖然上面的例子比較簡(jiǎn)單奈附，但是方法總是這樣的。

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

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

而尾遞歸在歸的過(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í)上解藻，如果你寫(xiě)出了一個(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)容摘自怎么寫(xiě)一個(gè)遞歸程序

最后編輯于：2018.09.02 22:07:23

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末涂籽，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子砸抛，更是在濱河造成了極大的恐慌评雌，老刑警劉巖，帶你破解...
沈念sama閱讀 221,888評(píng)論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件直焙，死亡現(xiàn)場(chǎng)離奇詭異景东，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)奔誓，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,677評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)斤吐，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人厨喂，你說(shuō)我怎么就攤上這事和措。” “怎么了蜕煌？”我有些...
開(kāi)封第一講書(shū)人閱讀 168,386評(píng)論 0贊 360
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵派阱，是天一觀的道長(zhǎng)。經(jīng)常有香客問(wèn)我斜纪，道長(zhǎng)贫母，這世上最難降的妖魔是什么？我笑而不...
開(kāi)封第一講書(shū)人閱讀 59,726評(píng)論 1贊 297
?港島之戀（遺憾婚禮）
正文為了忘掉前任盒刚，我火速辦了婚禮腺劣，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘伪冰。我一直安慰自己誓酒，他們只是感情好樟蠕，可當(dāng)我...
茶點(diǎn)故事閱讀 68,729評(píng)論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布贮聂。她就那樣靜靜地躺著靠柑，像睡著了一般。火紅的嫁衣襯著肌膚如雪吓懈。梳的紋絲不亂的頭發(fā)上歼冰，一...
開(kāi)封第一講書(shū)人閱讀 52,337評(píng)論 1贊 310
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音耻警，去河邊找鬼隔嫡。笑死，一個(gè)胖子當(dāng)著我的面吹牛甘穿，可吹牛的內(nèi)容都是我干的腮恩。我是一名探鬼主播，決...
沈念sama閱讀 40,902評(píng)論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼温兼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼秸滴！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起募判，我...
開(kāi)封第一講書(shū)人閱讀 39,807評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤荡含，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后届垫，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體释液，經(jīng)...
沈念sama閱讀 46,349評(píng)論 1贊 318
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,439評(píng)論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年装处，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了误债。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 40,567評(píng)論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡符衔，死狀恐怖找前，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情判族，我是刑警寧澤躺盛，帶...
沈念sama閱讀 36,242評(píng)論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站形帮，受9級(jí)特大地震影響槽惫，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜辩撑，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,933評(píng)論 3贊 334
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一界斜、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧合冀，春花似錦各薇、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 32,420評(píng)論 0贊 24
一樁弒父案峭判，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)开缎。三九已至，卻和暖如春林螃，著一層夾襖步出監(jiān)牢的瞬間奕删，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 33,531評(píng)論 1贊 272
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工疗认，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留完残，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,995評(píng)論 3贊 377
代替公主和親
正文我出身青樓横漏，卻偏偏與公主長(zhǎng)得像谨设，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子缎浇，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,585評(píng)論 2贊 359