程序函数递归原理讲解
一、栈
在说函数递归的时候，顺便说一下栈的概念。
栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每个程序中都是存在的，它不需要程序员编写代码去维护，而是由运行是系统自动处理。所谓的系统自动维护，实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们，但程序员应该对此有所了解。
再来看看程序中的栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时，运行时系统将把调用者的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时，系统把被调用者的自变量压入到栈中，并把栈指针再向下移，以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后，被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其他自变量也是存放在栈中的。由于这些进栈操作，栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针，以他为参考，用正或负的偏移值来访问栈中的变量。当被调用者准备返回时，系统弹出栈中所有的自变量，这时栈指针移动了被调
用者刚开始执行时的位置。接着被调用者返回，系统从栈中弹出返回地址，调用者就可以继续执行了。当调用者继续执行时，系统还将从栈中弹出调用者的实参，于是栈指针回到了调用发生前的位置。
可能刚开始学的人看不太懂上面的讲解，栈涉及到指针问题，具体可以看看一些数据结构的书。要想学好编程语言，数据结构是一定要学的。
二、递归
递归，是函数实现的一个很重要的环节，很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级函数中调用自己。
递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝，这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础，是使得递归成为可能。假定某个调用函数调用了一个被调用函数，再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能正常工作。程序遍历执行这些函数的过程就被称为递归下降。
程序员需保证递归函数不会随意改变静态变量和全局变量的值，以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程，并且返回到顶层。
例如这样的程序就是递归：
void a(int);
main()
{
intnum=5;
a(num);
}
void a(intnum)
{
if(num==0) return;
printf(%d,num);
a(--num);
}
在函数a()里面又调用了自己，也就是自己调用本身，这样就是递归。那么有些人可能要想，这不是死循环吗？所以在递归函数中，一定要有return 语句，没有return语句的递归函数是死循环。
我们分析上面的例子，先调用a(5)，然后输出5，再在函数中调用本身a(4)，接着回到函数起点，输出4，……，一直到调用a(0)，这时发现已经满足if
条件，不在调用而是返回了，所以这个递归一共进行了5次。如果没有这个return，肯定是死循环的。
虽然递归不难理解，但是很多在在使用递归函数的时候，问题多多。这里面一般有两个原因：一是如何往下递归，也就是不知道怎么取一个变量递归下去；二是不知道怎么终止递归，经常弄个死循环出来。
下面看几个例子：
1.求1+2+……+100的和
先分析一下。第一递归变量的问题，从题目上看应该取1,2,……,100这些变量的值作为递归的条件；第二就是如何终止的问题，从题目上看应该是当数为100的时候就不能往下加了。那么我们试着写一下程序。
int add(int);
main()
{
intnum=1,sn;
sn=add(num);
printf(%d\n,sn);
getch();
}
int add(intnum)
{
static intsn;
sn+=num;
if(num==100) return sn;
add(++num);
}
分析一下程序：前调用add(1)，然后在子函数中把这个1加到sn上面。接着调用add(2)，再把sn加2上来。这样一直到100，到了100的时候，先加上来，然后发现满足了if条件，这时返回sn的值，也就是1+2+……+100的值了。
这里有一个问题一定要注意，就是static intsn;
有些人就不明白，为什么要使用static类型修饰符，为什么不使用intsn=0;？如果使用intsn=0;这样的语句，在每次调用函数add()的时候，sn的值都是赋值为0,也就是第一步虽然加了1上来，可是第二次调用的时候，sn又回到了0。我们前面说了，static能保证本次初始化的值是上次执行后的值，这样也就保证了前面想加的结果不会丢失。如果你修改为intsn=0，最后结果一定是最后的100这个值而不是5050。
2.求数列s(n)=s(n-1)+s(n-2)的第n项。其中s(1)=s(2)=1。
可以看出，终止条件一定是s(1)=s(2)=1。递归下降的参数一定是n。
int a(int);
main()
{
intn,s;
scanf(%d,&n);
s=a(n);
printf(%d\n,s);
getch();
}
int a(int n)
{
if(n<3) return 1;
return a(n-1)+a(n-2);
}
这个题目主要说明的是，在函数中，不一定只有一个return语句，可以有很多，但是每次对归的时候只有一个起作用。题目不难理解，这儿不分析了。
说了这些递归，其实它和函数的调用没有大的区别，主要就是一个终止条件要选好。递归函数很多时候都能用循环来处理。
main()
{
int n=20,array[20];
inti;
for(i=0;i { if(i<2) array[i]=1; else array[i]=array[i-1]+array[i-2]; } printf(%d\n,array[19]); getch(); } 上面的程序就是实现一模一样的功能的。但是它有一个缺陷，就是n的值不是通过键盘输入来得到。如果想通过键盘来得到n，可以这样： main() { intn,i; int s1=1,s2=1,temp scanf(%d,&n); for(i=3;i<=n;i++) { temp=s2; s2+=s1; s1=temp; } printf(%d\n,s2); getch(); } 但是在某些场合，使用递归比使用循环要简单的多。而且有些题目，一看就知道应该使用递归而不是循环来处理。 递归调用详解，分析递归调用的详细过程 2009年05月23日星期六 22:52 一、栈 在说函数递归的时候，顺便说一下栈的概念。 栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每个程序中都是存在的，它不需要程序员编写代码去维护，而是由运行是系统自动处理。所谓的系统自动维护，实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们，但程序员应该对此有所了解。 再来看看程序中的栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时，运行时系统将把调用者的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时，系统把被调用者的自变量压入到栈中，并把栈指针再向下移，以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后，被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其他自变量也是存放在栈中的。由于这些进栈操作，栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针，以他为参考，用正或负的偏移值来访问栈中的变量。当被调用者准备返回时，系统弹出栈中所有的自变量，这时栈指针移动了被调用者刚开始执行时的位置。接着被调用者返回，系统从栈中弹出返回地址，调用者就可以继续执行了。当调用者继续执行时，系统还将从栈中弹出调用者的实参，于是栈指针回到了调用发生前的位置。 可能刚开始学的人看不太懂上面的讲解，栈涉及到指针问题，具体可以看看一些数据结构的书。要想学好编程语言，数据结构是一定要学的。 二、递归 递归，是函数实现的一个很重要的环节，很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级 算法设计的特征：有穷性，确定性，输入和输出，可行性 运行算法的时间：硬件的速度。书写程序的语言。问题的规模，编译生成程序的代码质量算法复杂度: 时间复杂度和空间复杂度 1．迭代法 迭代法又称为辗转法，是用计算机解决问题的一种基本方法，为一种不断用变量的旧值递推新值的过程，与直接法相对应，一次性解决问题。迭代法分为精确迭代和近似迭代，“二分法”和“牛顿迭代法”属于近似迭代法。迭代法利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。 利用迭代算法解决问题，需要做好以下三个方面的工作： 1.确定迭代变量（在可以用迭代算法解决的问题中，至少存在一个直接或间接地 不断由旧值递推出新值的变量，这个变量就是迭代变量。） 2. 建立迭代关系式（所谓迭代关系式，指如何从变量的前一个值推出其下一个值 的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以顺推 或倒推的方法来完成。） 3.对迭代过程进行控制（在什么时候结束迭代过程？这是编写迭代程序必须考虑 的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为 两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所 需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实 现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程 的条件。） 2．穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从众找出那些符合要求的候选解作为问题的解。 即本方法使用可以理解为暴力循环方法，穷举所有可能性，一般这种方法的时间效率太低，不易使用。但是方法简单，易理解。 3．递推法 递推是计算机数值计算中的一个重要算法，思路是通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机长于重复处理的特点。递推法: 递推法实际上是一种递推关系，就是为了得到问题的解，把它推到比原问题简单的 问题求解，可分为顺推法和倒推法。 i.顺推法，就是先找到递推关系式，然后从初始条件出发，一步步地按 递推关系式递推，直至求出最终结果。 ii.倒推法，就是在不知道初始条件的情况下，经某种递推关系而获知问题的解，再倒过来，推知它的初始条件。 4．递归法（递推加回归） 一个过程或函数在其定义或说明中又间接或间接调用本身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题类似的规模较小的问题来求解，递 归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了 程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想 写出的程序往往十分简洁易懂。 一般来说，递归需要有边界条件、递归前进段和递归前往段。当边界条件不满脚时，递归前进;当边界条件满脚时，递归前往。 递 归 冯文科 一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引 用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及n a 与前面临近几项之间的关系。 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： ???>==-1 ,1,11n na n a n n 如果需要写一个函数来求n a 的值，那么可以很容易地写成这样： 这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一 些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为 特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。 以上面求阶乘数列的函数)(n f 为例。如在求)3(f 时，由于3不是特殊值，因此需要计 算)2(*3f ，但)2(f 是对它自己的调用，于是再计算)2(f ，2也不是特殊值，需要计算 )1(*2f ，需要知道)1(f 的值，再计算)1(f ，1是特殊值，于是直接得出1)1(=f ，返回上 一步，得2)1(*2)2(==f f ，再返回上一步，得62*3)2(*3)3(===f f ，从而得最终解。 用图解来说明，就是 下面再看一个稍复杂点的例子。 【例1】数列}{n a 的前几项为 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i; 递归算法详解标准化管理处编码[BBX968T-XBB8968-NNJ668-MM9N] 递归 冯文科一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简 a与前面临近几项之间的关单，于是人们想出另一种办法来描述这种数列：通过初值及 n 系。 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： a的值，那么可以很容易地写成这样： 如果需要写一个函数来求 n 这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。 以上面求阶乘数列的函数) f为例。如在求)3(f时，由于3不是特殊值，因此需 (n 要计算)2( 3f，但)2(f是对它自己的调用，于是再计算)2(f，2也不是特殊值，需要计 * 算)1( f，返回 )1(= 2f，需要知道)1(f的值，再计算)1(f，1是特殊值，于是直接得出1 * 上一步，得2 3 * )2( )3(= = f，从而得最终 =f )1( 3 2 * * )2(= =f 2 f，再返回上一步，得6 解。 用图解来说明，就是 Make By Mr.Cai 思路介绍： 首先，可证明，当盘子的个数为n 时，移动的次数应等于2^n - 1。 然后，把三根桩子按一定顺序排成品字型（如：C ..B .A ），再把所有的圆盘按至上而下是从小到大的顺序放在桩子A 上。 接着，根据圆盘的数量确定桩子的排放顺序： 若n 为偶数，按顺时针方向依次摆放C ..B .A ； 若n 为奇数，按顺时针方向依次摆放B ..C .A 。 最后，进行以下步骤即可： （1）首先，按顺时针方向把圆盘1从现在的桩子移动到下一根桩子，即当n 为偶数时，若圆盘1在桩子A ，则把它移动到B ；若圆盘1在桩子B ，则把它移动到C ；若圆盘1在桩子C ，则把它移动到A 。 （2）接着，把另外两根桩子上可以移动的圆盘移动到新的桩子上。 即把非空桩子上的圆盘移动到空桩子上，当两根桩子都非空时，移动较小的圆盘。 （3）重复（1）、（2）操作直至移动次数为2^n - 1。 #include } void Push(int top)//进栈 { s[++this->top]=top; } void setNext(Stake *p) { next=p; } Stake *getNext()//获取下一个对象的地址 { return next; } int getName()//获取当前桩子的编号 { return name; } private: int s[Cap+1];//表示每根桩子放盘子的最大容量 int top,name; Stake *next; }; void main() { int n; void hanoi(int,int,int,int); cout<<"请输入盘子的数量："; cin>>n; if(n<1) cout<<"输入的盘子数量错误!!!"< 递归算法详解 C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。 许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐怖。 这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。 我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以我们需要在余数上加上48来获得正确的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII码是48，所以我们用余数加上‘0’，所以有下面的关系： ‘0’+ 0 =‘0’ ‘0’+ 1 =‘1’ ‘0’+ 2 =‘2’ ... 从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。 这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。 我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。 这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身。 在程序中，递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。 /*接受一个整型值（无符号0，把它转换为字符并打印它，前导零被删除*/ 通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口. 从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的. ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现同步. 下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式). 下面以先序遍历来说明: void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法*/ { if (T) { visit(T); /* 访问当前结点*/ preorder_recursive(T->lchild); /* 访问左子树*/ preorder_recursive(T->rchild); /* 访问右子树*/ } } visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->lchild)就是把当前数据变换为它的左子树,访问右子树的操作可以同样理解了. 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的"叶子结点". 1.用递归法计算n! 【讲解】 递归是算法设计中的一种基本而重要的算法。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。 递归方法具有易于描述、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。 递归概述 一个函数在它的函数体内调用它自身称为递归（recursion）调用。是一个过程或函数在其定义或说明中直接或间接调用自身的一种方法，通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 使用递归要注意以下几点： （1）递归就是在过程或函数里调用自身； （2）在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。 例如有函数r如下： int r(int a) { b=r(a?1); return b; } 这个函数是一个递归函数，但是运行该函数将无休止地调用其自身，这显然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。 构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是递推描述的。 例4-1 用递归法计算n!。 n!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。 （1）描述递归关系 递归关系是这样的一种关系。设{U 1,U 2 ,U 3 ,…,U n ,…}是一个序列，如果从某一项k开始， U n 和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。 注意到，当n≥1时，n!=n*(n?1)!（n=0时，0!=1），这就是一种递归关系。对于特定的k!，它只与k与(k?1)!有关。 （2）确定递归边界 在步骤1的递归关系中，对大于k的U n 的求解将最终归结为对U k 的求解。这里的U k 称 为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。 确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序： #include 递归程序设计 1．计算最大约数gcd(m,n)可用递归形式定义如下：若m%n等于0，则gcd(m,n)等于n 否则，gcd(m,n)等于gcd(n,m%n)。 #include else return gcd(n , m %n ); } int main(){ int m, n; cout << "n="; cin >> n; cout << "m="; cin >> m; cout << gcd(m, n); system("pause"); return 0; }。 2．编写一递归函数，计算下面的级数： i i m 1......31211)(++++= #include 案例一： publicclass Fibonacci { //一列数的规则如下: 1、1、2、3、5、8、13、21、34 ，求第30位数是多少？使用递归实现 publicstaticvoid main(String[] args){ System.out.println(Fribonacci(9)); } publicstaticint Fribonacci(int n){ if(n<=2) return 1; else return Fribonacci(n-1)+Fribonacci(n-2); } } 案例二： publicclass Hanio1 { /* * 汉诺塔（又称河内塔）问题其实是印度的一个古老的传说。开天辟地的神勃拉玛（和中国的盘古差不多的神吧）在一个庙里留下了三根金刚石的棒， * 第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上， * 规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖(移动圆片的次数)18446744073709551615， * 众僧们即便是耗尽毕生精力也不可能完成金片的移动了。 *要求：输入一个正整数n，表示有n个盘片在第一根柱子上。输出操作序列，格式为“移动 t从 x 到y”。每个操作一行， *表示把x柱子上的编号为t的盘片挪到柱子y上。柱子编号为A，B，C，你要用最少的操作把所有的盘子从A柱子上转移到C柱子上。 */ publicstaticvoid main(String[] args){ int i=3; char a ='A',b='B',c='C'; hanio(i,a,b,c); } publicstaticvoid hanio(int n,char a,char b,char c){ if(n==1) System.out.println("移动"+n+"号盘子从"+a+"到"+c); else{ hanio(n-1,a,c,b);//把上面n-1个盘子从a借助b搬到c System.out.println("移动"+n+"号盘子从"+a+"到"+c);//紧接着直接把n搬动c hanio(n-1,b,a,c);//再把b上的n-1个盘子借助a搬到c } } } 案例三： publicclass Rabbit { /* 古典问题：3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ 分析：首先我们要明白题目的意思指的是每个月的兔子总对数；假设将兔子分为小中大三种，兔子从出生后三个月后每个月就会生出一对兔子， 那么我们假定第一个月的兔子为小兔子，第二个月为中兔子，第三个月之后就为大兔子，那么第一个月分别有1、0、0，第二个月分别为0、1、0， 第三个月分别为1、0、1，第四个月分别为,1、1、1，第五个月分别为2、1、2，第六个月分别为3、2、3，第七个月分别为5、3、5…… 兔子总数分别为：1、1、2、3、5、8、13…… 于是得出了一个规律，从第三个月起，后面的兔子总数都等于前面两个月的兔子总 一分而治之算法 分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。下列通过实例加以说明。 例：利用分而治之算法求一个整数数组中的最大值。 练习：[找出伪币] 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。 二贪心算法 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪心算法(Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪心算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪 常用算法设计方法 要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0； （2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 { x0=初始近似根； do { x1=x0； x0=g(x1)；/*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon)； printf(“方程的近似根是%f\n”，x0)； } 迭代算法也常用于求方程组的根，令 X=（x0，x1，…，x n-1） 设方程组为： 递归算法详细分析－> C阅读(17418) C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。 许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐怖。 这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。 我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267 除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以我们需要在余数上加上48来获得正确的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII码是48，所以我们用余数加上‘0’，所以有下面的关系： ‘0’+ 0 =‘0’ ‘0’+ 1 =‘1’ ‘0’+ 2 =‘2’ ... 从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。 这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。 我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。 这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身。 汉诺塔C递归算法详细解答 程序如下： void move(char x,char y){ printf("%c-->%c\n",x,y); } void hanoi(intn,charone,chartwo,char three){ /*将n个盘从one座借助two座，移到three座*/ if(n==1) move(one,three); else{ hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); } } main(){ int n; printf("input the number of diskes:"); scanf("%d",&n); printf("The step to moving %3d diskes:\n",n); hanoi(n,'A','B','C'); } Hanoi塔问题, 算法分析如下，设A上有n个盘子。 如果n=1，则将圆盘从A直接移动到C。 如果n=2，则： （1）将A上的n-1（等于1）个圆盘移到B上； （2）再将A上的一个圆盘移到C上； （3）最后将B上的n-1（等于1）个圆盘移到C上。 如果n=3，则： A）将A上的n-1（等于2，令其为n`）个圆盘移到B（借助于C），步骤如下：（1）将A上的n`-1（等于1）个圆盘移到C上。 （2）将A上的一个圆盘移到B。 （3）将C上的n`-1（等于1）个圆盘移到B。 B）将A上的一个圆盘移到C。 C）将B上的n-1（等于2，令其为n`）个圆盘移到C（借助A），步骤如下：（1）将B上的n`-1（等于1）个圆盘移到A。 （2）将B上的一个盘子移到C。 （3）将A上的n`-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。 递归，作为C语言最经典的算法之一，是一种非常有用的程序设计方法。虽然用递归算法编写的程序结构清晰，具有很好的可读性，还往往使某些看起来不易解决的问题变得容易解决。但在递归函数中，由于存在着自调用过程，程序控制反复进入其自身，使程序的分析设计有一定困难，致使很多初学者往往对递归迷惑不解，也在这上面花了不少的时间，却收效甚微。那么，究竟什么是递归?怎么实现递归呢? 所谓递归，简而言之就是在调用一个函数的过程中又直接或间接地调用该函数本身，以实现层次数据结构的查询和访问。在函数中直接调用函数本身，称为直接递归调用。在函数中调用其它函数，其它函数又调用原函数，这就构成了函数自身的间接调用，称为间接递归调用。 而采用递归方法来解决问题，必须符合以下三个条件： 1、可以把要解决的问题转化为一个新问题，而这个新的问题的解决方法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减。 说明：解决问题的方法相同，调用函数的参数每次不同（有规律的递增或递减），如果没有规律也就不能适用递归调用。 2、可以应用这个转化过程使问题得到解决。 说明：使用其他的办法比较麻烦或很难解决，而使用递归的方法可以很好地解决问题 3、必定要有一个明确的结束递归的条件。 说明：一定要能够在适当的地方结束递归调用。不然可能导致系统崩溃。 好知道是这样以后;我们来写一个众多教材上的程序：使用递归的方法求n!。 当n>1时，求n!的问题可以转化为n*(n-1)!的新问题。比如n=4： 第一部分：4*3*2*1 n*(n-1)! 第二部分：3*2*1 (n-1)(n-2)! 第三部分：2*1 (n-2)(n-3)! 第四部分：1 (n-4)! 4-4=0，得到值1，结束递归。 我给的源程序如下： #include 复习 输入a,b,c,计算m 。已知m=) ,,max(),,max(),,max(c b b a c b b a c b a +?+ 请把求三个数的最大数max(x,y,z)定义成函数和过程两种方法作此题。 递 归 为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自已来定义自己的方法，称为递归定义。例如：定义函数f(n)为： /n*f(n －1) (n>0) f(n)= | \ 1(n=0) 则当n>0时，须用f(n-1)来定义f(n),用f(n-1-1)来定义f(n-1)……当n=0时，f(n)=1。 由上例我们可看出，递归定义有两个要素： （1） 递归边界条件。也就是所描述问题的最简单情况，它本身不再使用递归的定义。 如上例，当n=0时，f(n)=1，不使用f(n-1)来定义。 （2） 递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。 如上例：f(n)由f(n-1)定义，越来越靠近f(0),也即边界条件。最简单的情况是f(0)=1。 递归算法的效率往往很低, 费时和费内存空间. 但是递归也有其长处, 它能使一个蕴含递归关系且结构复杂的程序简介精炼, 增加可读性. 特别是在难于找到从边界到解的全过程的情况下, 如果把问题推进一步使其结果仍维持原问题的关系, 则采用递归算法编程比较合适. 递归按其调用方式分为: 1. 直接递归, 递归过程P 直接自己调用自己; 2. 间接递归, 即P 包含另一过程 D, 而D 又调用P. 递归算法适用的一般场合为: 1. 数据的定义形式按递归定义. 如裴波那契数列的定义: f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2. 对应的递归程序为: Function fib(n : integer) : integer; Begin if n = 0 then fib := 1 { 递归边界 } else if n = 1 then fib := 2 else fib := fib(n-2) + fib(n-1) { 递归 } End; 这类递归问题可转化为递推算法, 递归边界作为递推的边界条件. 2. 数据之间的关系(即数据结构)按递归定义. 如树的遍历, 图的搜索等. 3. 问题解法按递归算法实现. 例如回溯法等. 从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到" 尽头 "的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断" 回溯 "寻找解的方法, 称作" 回溯法 ". 例1、给定N （N>=1），用递归的方法计算1+2+3+4+…+（n-1）+n 。 分析与解答 本题是累加问题可以用递归方法求解。本题中，当前和=前一次和+当前项，而前一次和的计算方法与其相同，只是数据不同，即可利用s(n)=s(n-1)+n 来求解，另外递归调用的次数是有限次，且退出的条件是当n=1时s=1，这恰好符合递归算法的使用条件。 程序代码如下： program p_1(input,output); var s,t:integer; 3.5用递归法解决问题 【教材分析】 “用递归法解决问题”是《算法与程序设计》第三章第5节的内容，学业水平测试对本节内容也达到了B级要求，本节内容是在学习了VB基础知识中的三种基本结构，并且学习了数组、用解析法和穷举法解决问题等算法。本节先后介绍了“什么是递归法”、“自定义函数”、以及应用自定义函数结合递归算法来解决问题实例。通过本节内容的学习可以培养学生分析和分解问题的能力。从教材的结构上看“自定义函数”和“递归算法”是独立的，可以分别讲解，但在使用时两者是相辅相成的。 【学情分析】 这节课的教学对象是高中二年级学生，已经学习了算法与程序设计VB中的一些基础知识，初步了解了算法的概念。特点是在学习循环结构的过程中，学生已经积累了一些“递归”和“穷举”的算法。但是学生对函数尤其是“自定义函数”非常陌生，而“自定义函数”和“递归法”是本册的学习重点，也是以后编程的重点。学习本节内容学生可以充分体会递归算法的思想过程，扩大原来的知识面，进一步认识程序设计的功能，进一步激发学生学习算法与程序设计的兴趣。 【教学目标】 1．知识与技能： 理解什么是递归法，会用递归法的思想分析和解决问题 理解什么是自定义函数，能应用自定义函数实现递归算法的编程 2．过程与方法 学生通过思考、探究，体验递归算法和发现问题与解决问题的步骤 3．情感态度与价值观 在建立数学模型中培养学生的抽象思维能力，培养学生多维度思考问题和解决能力。 树立多学科整合的思想意识，能够用联系的观点解决问题。 【教学重点】 理解什么是递归算法，学会用递归法的思想分析问题。 理解自定义函数的概念。 【教学难点】 用自定义函数和递归算法编写程序解决问题 【教学方法及策略】递归调用详解,分析递归调用的详细过程
算法设计题详解
递归算法详解
算法设计及分析递归算法典型例题
递归算法详解完整版
汉诺塔问题非递归算法详解
递归算法详解
递归算法工作栈的变化详解
04.递归算法讲解
递归练习题(新、选)
递归算法经典案例
C语言经典算法详解
算法设计与分析(详细解析(含源代码))
(重要)递归(含代码执行过程解释)
汉诺塔C递归算法详细解答
C语言函数递归[1]
递归讲解
用递归法解决问题
相关主题
文本预览