数据结构学习笔记（五）——递归

先来看看什么是递归（recursion），它的简单定义是这样的：一个函数直接或间接调用自己。

为什么要用递归解决问题呢？递归可以把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。它的好处在于可以用简单的代码完成规模大的问题，N个问题可以转化为N-1个问题，那么解决N-1个问题只需要解决N-2个问题直到变成1个简单问题，最后逆向整个过程，从而完成求解。

在数学中，经常有这样一个问题，求出1+2+3+……+100的和。这类问题在中学的课程经常出现。用循环实现：

void main()
{
int sum,i;
sum=0;
for(i=1;i<=100;++i)
sum+=i;
printf("和为:%dn",sum);
}

循环的优点是，速度快，结构简单。但是并不能处理所有问题，像后面数据结构中树、图的部分问题本身只能用递归，或者是用递归实现起来较容易的汉诺塔的，八皇后等问题。

如果用递归的思想去考虑这个问题是怎样的呢？从

1加到100，用前面提到的思想翻译一下就是，把1到100的和拆分成100和1+..+99的和然后1到99又可以接着往下分成99和1+..+98的和，以此类推。这样就把一个复杂的问题拆分成一个简单问题的不断重复调用。

Long sum(int n) {
if(1 == n)
  return 1;
else 
  return n + sum(n-1);
}
int main() {
 printf(“和为%ld”,sum(100));
 return 0;
}

以上主函数调用了sum()函数，而sum()函数内部又调用了它自己。那么一个函数怎么自己调用的自己？

通常，当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成3件事：（1）将所有实在参数、返回地址等信息传递给被调用函数保存；（2）为被调用函数的局部变量分配存储区；（3）将控制转移到被调函数的入口。而从被调用函数返回调用函数之前，系统也应完成3件工作：（1）保存被调函数的计算结果；（2）释放被调函数的数据区；（3）依照被调函数保存的返回地址将控制转移到调用函数。当有多个构成嵌套调用时。按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当从一个函数退出时，就释放它的存储区，则当前正运行的函数的数据区必在栈顶。例如，在图（c）所示主函数main中调用了函数first，而在函数first中又调用了函数second，则（a）展示了当前正在执行函数second中某个语句时栈的状态，而（b）展示从函数second退出之后正执行函数first中某个语句时栈的状态（图中以语句标号表示返回地址）。(本段摘自《数据结构(C语言版) 严蔚敏 吴伟民 编著》)

三座塔中X塔从上至下从小到大有n个圆盘，要求将X上的n个圆盘移动至Z塔并保持原顺序，规定：

（1）每次只能移动一个圆盘

（2）任意时刻，都不能将大圆盘压在小圆盘之上。

把思路转换成伪算法

   如果是一个圆盘

        直接将A塔上的圆盘从A移到C

   否则

        先将A塔上的前n-1个圆盘借助C塔移到B

        直接将A塔上的圆盘从A移到C

        最后将B塔上的n-1个圆盘借助A塔移到C

#include <stdio.h>

void hanoi(int n, char A, char B, char C) {
  if(1 == n) {
    printf("将编号为%d的盘子直接从%c柱子移到%c柱子n",n, A, C);
  }else {
    hnt(n-1, A, C, B);
    printf("将编号为%d的盘子直接从%c柱子移到%c柱子n",n, A, C);
    hnt(n-1, B, A, C);
  }
}

int main() {
  char ch1 = 'A';
  char ch2 = 'B';
  char ch3 = 'C';
  int n;
  printf("请输入要移动盘子的个数：");
  scanf("%d",&n);
 hanoi(n, 'A', 'B', 'C');

  return 0;
}