什么是递归算法

递归算法就是一个函数通过不断对自己的调用而求得最终结果的一种思维巧妙但是开销很大的算法。

比如：

汉诺塔的递归算法：

void move(char x,char y){

printf("%c-->%c\n",x,y);

}

void hanoi(int n,char one,char two,char three){

/*将n个盘从one座借助two座，移到three座*/

if(n==1) move(one,three);

else{

hanoi(n-1...

递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。

移n个盘是已移n-1个盘为条件的，两者的共同点是移盘。所以可以用f（n）表示移n个盘，f(n-1)表示移n-1个盘，那么移n个盘和移n-1个盘有什么关系呢？

这就需要预先分析问题才能得出具体的关系

在这个问题中，把n个盘从a移到c需要三个步骤来完成。

1.n-1个盘从a移到b

2 1个盘从a移到c

3 n-1个盘从b移到c

已知n-1个盘从a移到b是可行的，为什么？

因为移1个盘是可行，那么移2个盘也是可行，移 3个盘是已移2个盘为条件的，所以移3个...

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。

标签：递归,算法