栈与递归
栈还有一个重要应用是在程序设计语言中实现递归。一个直接调用自己或通过一系列的调用语句间接的调用自己的函数，称为递归函数。
递归是程序设计中一个强有力的工具。
其一，有很多数学函数是递归定义的，如大家熟悉的阶乘函数：
| Fact(n)= | 1 | 若n=0 |
|---|---|---|
| n*Fact(n-1) | 若n>0 |
2阶Fibonacci数列：
| Fib(n)= | 0 | 若n=0 |
|---|---|---|
| 1 | 若n=1 | |
| Fib(n-1) + Fibz(n - 2) | 其他情形 |
Ackerman函数：
| Ack(m,n)= | n+1 | 若m=0 |
|---|---|---|
| Ack(m-1,1) | 若n=0 | |
| Ack(m-1,Ack(m,n-1)) | 其他情形 |
其二，有的数据结构，如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归的描述；
其三，还有一类问题，虽然问题本身没有明显的递归结构，但用递归求解比迭代求解更简单，如八皇后问题、Hanoi塔问题。
n阶Hanoi塔问题：
假设有3个分别命名为X、Y、Z的塔座，在塔座X上插有n个直径大小各不同、依小到大编号为1，2，...，n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则：
1.每次只能移动一个圆盘
2.圆盘可以插在X 、Y、Z中的任一塔座上
3.任何时刻都不能将一个较大的圆盘压在较小的圆盘上。
如何实现移动圆盘的操作呢?
当n=1时，问题比较简单，只要将编号为1的圆盘从塔座X直接移至塔座Z上即可；
当n>1时，需利用塔座Y作为辅助塔，若能设法将压在编号为n的圆盘之上的n-1个圆盘从塔座X移至塔座Y上，则可先将编号为n的圆盘从塔座X移至塔座Z上，然后再将塔座Y上的n-1个圆盘移至塔座Z上。
而如何将n-1个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题，只是问题的规模小1，因此可以用同样的方法求解。
TowerOfHanoi.c利用了前面的C封装的顺序栈对象 用线性表表示的顺序栈
实现了Hanoi塔递归移动的过程，每一步执行的过程以及x、y、z三个轴的状态均可以看到。
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); //将编号为1的圆盘从x移到z
//******************************打印步骤需要，非执行过程*********************
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上编号为1至n-1的圆盘移到y，z做辅助塔
x->pop(x,&elem);
z->push(z,&elem);//将编号为n的圆盘从x移到z
//******************************打印步骤需要，非执行过程*********************
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上编号为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
运行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
显然这是一个递归函数，在函数的执行函数中，需多次进行自我调用。那么，这个递归函数是如何执行的？
先看任意两个函数之间进行调用的情形：
与汇编程序中主程序和子程序之间的链接及信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数之间的链接及信息交换需通过栈来执行。
通常，当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成3件事：
1.将所有的实在参数、返回地址等信息传递给被调用函数保存。
2.为被调用函数的局部变量分配存储区。
3.将控制转移到被调函数入口。
而从被调用函数返回调用函数之前，系统也完成3件事：
1.保存被调函数的计算结果。
2.释放被调函数的数据区。
3.依照被调函数保存的返回地址将控制转移到调用函数。
当有多个函数构成嵌套调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须通过"栈"来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当从一个函数退出时，就释放它的存储区，则当前正运行的函数的数据区必在栈顶。
以下代码为例：
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;
...
}
主函数main中调用了函数first，而在函数first中又调用了函数second，
下图展示了当前正在执行函数second中某个语句时栈的状态，图中1，2表示返回地址：
image.png
下图展示了从函数second退出之后正执行函数first中某个语句时栈的状态，图中1表示返回地址：
image.png
一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数，因此，和每次调用相关的一个重要概念是递归函数运行的“层次”：
假设调用该递归函数的主函数为第0层，
则从主函数调用递归函数为进入第1层；
从第i层递归调用本函数为进入“下一层”，即第i+1层。
反之，退出第i层递归应返回至上一层。
为了保证递归函数正确执行，系统需设立一个"递归工作栈"作为整个递归函数运行期间使用的数据存储区。
每一层递归所需信息构成一个“工作记录”，其中包括所有的实在参数、所有的局部变量以及上一层返回的地址。
每进入一层递归，就产生一个新的工作记录压入栈顶。
每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。
由于递归函数结构清晰，程序易读，而且它的正确性容易得到证明，因此，利用允许递归调用的语言进行程序设计时，给用户编制程序带来很大方便。因为对这样一类递归问题编程时，不需要用户自己而由系统来管理递归工作栈。
理解递归
在初学递归的时候, 看到一个递归实现, 我们总是难免陷入不停的回溯验证之中, 因为回溯就像反过来思考迭代, 这是我们习惯的思维方式, 但是实际上递归不需要这样来验证。
比如, 阶乘的计算：
阶乘的定义: “一个正整数的阶乘（英语：factorial）是所有小于或等于该数的正整数的积，并且0的阶乘为1。”
代码实现：
int Fact(int n){
if(n<=1){
return 1;
}else{
return n * Fact(n - 1);
}
}
我们怎么判断这个阶乘的递归计算是否是正确的呢?
回溯的思考方式是这么验证的, 比如当n = 4时, 那么Fact(4)等于4 *Fact(3), 而Fact(3)等于3 * Fact(2), Fact(2)等于2 * Fact(1), 等于2 * 1, 所以Fact(4)等于4 * 3 * 2 * 1. 这个结果正好等于阶乘4的迭代定义。
用回溯的方式思考虽然可以验证当n = 某个较小数值是否正确, 但是其实无益于理解。
Paul Graham提到一种验证方法：
当n=0, 1的时候, 结果正确，
假设函数对于n是正确的, 函数对n+1结果也正确，
如果这两点是成立的，我们知道这个函数对于所有可能的n都是正确的。
这种方法很像数学归纳法, 也是递归正确的思考方式。
如何找到一个适用递归算法的问题
上面讲了怎么理解递归是正确的, 同时可以看到在有递归算法描述后, 其实程序很容易写, 那么最关键的问题就是, 我们怎么找到一个问题的递归算法呢?
Paul Graham提到, 你只需要做两件事情:
你必须要示范如何解决问题的一般情况, 通过将问题切分成有限小并更小的子问题。
你必须要示范如何通过有限的步骤, 来解决最小的问题(基本用例)。
如果这两件事完成了, 那问题就解决了。因为递归每次都将问题变得更小, 而一个有限的问题终究会被解决的, 而最小的问题仅需几个有限的步骤就能解决。
在什么情况下用递归
递归并不一定适用所有情况, 很多情况用迭代远远比用递归好了解；其次, 相对来说, 递归的效率往往要低于迭代的实现，同时, 内存消耗也会更大。
以上面的阶乘算法为例，如果n = 100，很显然这段程序需要递归地调用自身100次。这样调用深度至少就到了100。栈的大小是有限的，当n变的更大时，有朝一日总会使得栈溢出，从而程序崩溃。除此之外，每次函数调用的开销会导致程序变慢。所以说这段程序十分不好。
什么是好的递归：如果递归能够将问题的规模缩小，那就是好的递归。
怎样才算是规模缩小了呢。举个例子，比如要在一个有序数组中查找一个数，最简单直观的算法就是从头到尾遍历一遍数组，这样一定可以找到那个数。如果数组的大小是N，那么我们最坏情况下需要比较N次，所以这个算法的复杂度记为O(N)。有一个大名鼎鼎的算法叫二分法，它的表达也很简单，由于数组是有序的，那么找的时候就从数组的中间开始找，如果要找的数比中间的数大，那么接着查找数组的后半部分(如果是升序的话)，以此类推，知道最后找到我们要找的数。稍微思考一下可以发现，如果数组的大小是N，那么最坏情况下我们需要比较logN次(计算机世界中log的底几乎总是2)，所以这个算法的复杂度为O(logN)。
简单的分析一下二分法为什么会快。可以发现二分法在每次比较之后都帮我们排除了一半的错误答案，接下去的一次只需要搜索剩下的一半，这就是说问题的规模缩小了一半。而在直观的算法中，每次比较后最多排除了一个错误的答案，问题的规模几乎没有缩小(仅仅减少了1)。这样的递归就稍微像样点了。
重新看阶乘的递归，每次递归后问题并没有本质上的减小(仅仅减小1)，这和简单的循环没有区别，但循环没有函数调用的开销，也不会导致栈溢出。所以结论是如果仅仅用递归来达到循环的效果，那还是改用循环吧。
总结一下，递归的意义就在于将问题的规模缩小，并且缩小后问题并没有发生变化(二分法中，缩小后依然是从数组中寻找某一个数)，这样就可以继续调用自身来完成接下来的任务。我们不用写很长的程序，就能得到一个十分优雅快速的实现。
如何写递归
以二分查找算法为例子，首先给出函数原型，返回值是元素在数组中的位置，如果查找失败返回-1。：
int binarySearch(int *array,int start,int end,int num_wanted)
1.基准情况
基准情况其实就是递归的终止条件。其实在实际中，这是十分容易确定的。例如在二分查找中，终止条件就是找到了我们想要的数或者搜索完了整个数组(查找失败)。
if(end < start){
return -1;
}else if(num_wanted == array[middle]){
return middle;
}
2.不断演进
演进的过程就是我们思考的过程，二分查找中，就是继续查找剩下的一半数组。
if(num_wanted > array[middle]){
index = binarySearch(array,middle + 1,end,num_wanted);
}else{
index = binarySearch(array,start,middle - 1,num_wanted);
}
3.用人的思考方式设计
这条法则我认为是非常重要的，它不会出现在编码中，但却是理解递归的一条捷径。它的意思是说，在一般的编程实践中，我们通常需要用大脑模拟电脑执行每一条语句，从而确定编码的正确性，然而在递归编码中这是不需要的。递归编码的过程中，只需要知道前两条法则就够了。之后我们就会看到这条法则的如何工作的了。
4. 不要做重复的事情
在任何编码中，这都是不应该出现的事情，但是在递归中这更加可怕，可能由于一次多余的递归使得算法增加数级复杂度。
完整的二分法的程序：
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都已经在前两条法则的实现中了。
1不必多说，4是一个比较关键的步骤，经常容易被忘记。
这里就用到第3条法则，编写的时候只要认为2或者3一定会正确运行，并且立刻返回，
不要考虑2和3内部是如何运行的，因为这就是你现在在编写的。
这样4该如何处理就是显而易见的了，在这里只需要将找到的index返回就可以了。
第4条法则在这个例子里并没有出现，我们可以看一下斐波那契数列的递归实现。
long int fib(int n){
if(n <= 1){
return 1;
}else{
return fib(n-1) + fib(n-2); // 1
}
}
乍看之下，这段程序很精练，它也是一段正确的递归程序，有基准条件、不断推进。但是如果仔细分析一下它的复杂度可以发现，如果我们取n=N，那么每次fib调用会增加额外的2次fib调用(在1处)，即fib的运行时间T(N) = T(N-1) + T(N-2)，可以得到其复杂度是O(2^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);
}
}
上面就是去除递归后的二分查找的程序，我们只需要在程序开头处加上一个标号，在原本递归调用处修改参数的值并goto到标号就能完成这个工作。
事实上，如果你写出了一个尾递归程序，在编译的时候编译器很可能就这样帮你优化了。当然这样的程序非常不符合我们的习惯，它实际上是将递归转化为了循环。
循环还是应当使用while或者for实现，仔细地将上面这段程序改成while循环就成了这样。
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;
}
}
这样就更加符合我们的习惯了，它比递归的版本速度略有提高，最重要的是不会导致栈溢出。
部分内容摘自怎么写一个递归程序
