数据结构学习笔记：递归
通常，当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需完成3件事：
1）、将所有的实参、返回地址等信息运输传递给被调用函数保存。
2）、为被调用函数的局部变量分配存储区。
3）、将控制转移到被调用函数的入口。
而从被调用函数返回调用函数之前，系统也应该完成3件工作：
1）、保存被调函数的计算结果。
2）、释放被调函数的数据区。
3）、依照被调函数保存的返回地址将控制转移到调用函数。
当有多个函数构成嵌套调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈的顶区分配一个存储区，每当从一个函数退出时，就释放它的存储区，则当前正运行的函数的数据区必在栈顶。
程序例子
1+2+3+4+.,...+100：
int sum(int n)
{
if (n == 1)
{
return n;
}
else
{
return n + sum(n - 1);
}
}
汉诺塔：
void move(char A, char C)
{
printf("从%c移到%c
", A, C);
}
void HanNuoTa(char A, char B, char C, int n)
{
if (n == 1)
printf("从%c移到%c
", A, C);
else
{
HanNuoTa(A, C, B, n - 1);
printf("从%c移到%c
", A, C);
HanNuoTa(B, A, C, n - 1);
}
}
下一篇：
设计模式之适配器模式（六）