一般定义（来自网络）：在调用一个函数的过程中又出现直接或间接地调用该函数本身，就是函数的递调用。
为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
递归算法的执行过程分递推和回归两个阶段。
在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。
在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。
在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。
当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。
总结一下：
1：递归算法的思想
递归算法是把问题转化为规模缩小了的同类问题的子问题。
然后递归调用函数（或过程）来表示问题的解。
在C语言中的运行堆栈为他的存在提供了很好的支持，过程一般是通过函数或子过程来实现。
递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。
2：递归算法的特点：
递归算法是一种直接或者间接地调用自身算法的过程。
在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
3：递归算法的要求
递归算法所体现的“重复”一般有三个要求：
一是每次调用在规模上都有所缩小(通常是减半)；
二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
我们看看几个经典递归问题
使用递归来解决斐波那契数列的第n个数是多少？（初始默认前两个值是 1,2）斐波那契数列简单来说就是下一个数是前两个数的总和。不知道这个的话请自行google脑补一下。利用递归思想，可以写成如下代码
int is_recursive_fib(int index){
if(index == 1 || index == 2){
return index;
}else{
return is_recursive_fib(index - 1) + is_recursive_fib(index - 2 );
}
}
当index为 1 或者 2 的时候，就直接返回 index的值；
当index不为 1 或者 2 的时候，就返回is_recursive_fib(index - 1) + is_recursive_fib(index - 2 )；
二话不说，先上个小图分析分析(毕竟没有绘画功底，见谅)
1.jpg
假设求第五个数，它的值是多少。
分析过程如下：
第一步，调用函数 传递参数是 5； 见 ①
第二步，拆解为 f(4) + f(3)； 见 ②
第三步，将左边的f(4) 拆解为 f(3) + f(2)；见 ③
第四步，将第三步分解出来f(3),再次拆分为 f(2) + f(1)； 见 ④
这个时候根据返回条件 index 是 1 或者 2，就开始返回回去；
第五步，将f(2) + f(1) = 3的值返回回去； 见⑤
这个时候f(3)得到返回的值 3， 然后和f(2) 相加计算得到值 是 5
第六步，将f(3) + f(2)的值为 5， 返回给 f(4);见 ⑥
这个时候 f(4)得到值 就是 5
第七步，拆解右边的 f(3)为 f(2) + f(1); 见 ⑦
这个时候 index为 1 和 2，满足返回条件
第八步，将 f(2) + f(1)的值 为 3 返回给 f（3）；见 ⑧
第九步，将左边 f(4) 的值 5 和 右边 f(3)的值 3 相加， 然后返回给 f（5）；见⑨
最后，我们就得到f(5)的结果是 8.
前面已经提到使用递归，解决问题思路上会很简单，但是效率却非常低。
我们来改写一下如果上面例子不用递归方法来实现，改用 for循环迭代计算看看效果如何。
先上代码
int not_recursive_fib(int index){
if(index == 1 || index == 2){
return index;
}
int array[index+1];
array[1] = 1;
array[2] = 2;
int i=0;
for(i = 3;i<=index; i++){
array = array[i-1] + array[i-2];
}
return array[index];
}
这个算法可以简单看出 如果是 1 或者 2 就直接返回了结果。
如果大于2的话， 怎定义一个数组， 在for 循环那里，每一次计算下一个值，下标从3开始。
但是比较一下两个的效率如何：
同一台电脑设备前提下， 我们设置求第45个值是多少
2.png
相比之下，用递归方法的 比 不是用递归方法的效率居然差 5倍之多！ 本文章例子在CodeBlocks 13.12版本测试通过**recursion.c
给一道课外习题
汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。如果只有一个盘子，则不需要利用B座，直接将盘子从A移动到C。
3.gif
参考答案
/**
*
Tutorial 汉诺（Hanoi）塔问题
show the steps how to move one by one
Author: hejing
Email: 2010jing@gmail.com
Date : 2015/11/3
*
**/
#include <stdio.h>
void move(char x,char y); // 对move函数的声明
void hanoi(int n,char one,char two,char three) ;// 对hanoi函数的声明
int count = -1;
int main()
{
//hanoi函数
int m;
printf("请输入一共有多少个板子需要移动:");
scanf("%d",&m);
printf("以下是%d个板子的移动方案:\n",m);
hanoi(m,'A','B','C');
return 0;
}
// 定义hanoi函数
// 将n个盘从one座借助two座,移到three座
void hanoi(int n,char one,char two,char three)
{
if(n==1)
move(one,three);
else
{
hanoi(n-1,one,three,two); //首先把n-1个从one移动到two
move(one,three); //然后把最后一个n从one移动到three
hanoi(n-1,two,one,three); //最后再把n-1个从two移动到three
}
}
void move(char x,char y) // 定义move函数
{
count++;
if( !(count%5) )
printf("\n");
printf("%c移动至%c ",x,y);
}
网友评论