搜索

算法精解-C语言描述 递归和尾递归 (图解+实例)

gecimao 发表于 2019-07-01 13:22 | 查看: | 回复:

  让我们来观察一下自然界中出现的递归现象:蕨类植物的叶子,每片叶子叶脉中的小分支都是整片叶子的较小缩影;又或者两个反光的物体,相互映射对方渐远的影像。这样的例子使我们明白,尽管大自然的力量是强大的,在许多方面它那种出乎意料的简洁更让我们觉得优美。同样的道理也可以用在递归算法上,从很多方面来说递归算法都是简洁而优美的,而且非常强大。

  在计算机科学领域中,递归是通过函数来实现的。递归函数是一种可以调用自身的函数。

  假设我们想计算整数n的阶乘。n的阶乘可能写作n!,其结果是1~n之间的各数之积。比如,4!=4 x 3 x 2 x 1。一种方法是循环遍历其中的每一个数,然后与它之前的数相乘作为结果再参与下一次计算。这种方法称为迭代法,可以正式定义为:

  看待这个问题的另一种方式是将n!定义为更小的阶乘形式。我们将n!定义为n-1阶乘的n倍。再把(n-1)!定义为n-1倍的(n-2)!,(n-2)!看作(n-2)倍的(n-3)!,一直到n=1时,我们就计算完了。这就是递归的方式,可以正式定义为:

  上图(1)展示了利用递归计算4!的过程。它也说明了递归过程中的两个基本阶段:递推和回归。在递推阶段,每一个递归调用通过进一步调用自己来记住这次递归过程。当其中有调用满足终止条件时,递推结束。比如,在计算n!时,终止条件是当n=1和n=0,此时函数只需简单的返回1即可。每一个递归函数都必须拥有至少一个终止条件;否则递推阶段永远不会结束了。一旦递推阶段结束,处理过程就进入回归阶段,在这之前的函数调用以逆序的方式回归,直到最初调用的函数为止,此时递归过程结束。

  C函数fact的工作方式如下:它接受一个整数n作为参数,如果n小于0,该函数直接返回0,这代表一个错误。如果n等于0或1,该函数返回1,这是因为0!和1!都等于1,以上是终止递归的条件。否则,函数返回n-1的阶乘的n倍。而n-1的阶乘又会以递归的方式再次调用fact来计算,如此继续。

  为理解递归究竟是如何工作的,有必要先看看C语言中函数的执行方式。我们先来看看C程序在内存中的组织方式(见图2-a)。基本上,一个可执行程序由4个区域组成:代码段、静态数据区、堆与栈。代码段包含程序运行时所执行的机器指令。静态数据区包含在程序生命周期内一直持久的数据,比如全局变量和静态局部变量。堆包含程序运行时动态分配的存储空间,比如malloc分配的内存。栈包含函数调用的信息。

  当C中调用了一个函数时,栈中会分配一块空间来保存与这个调用相关的信息。每一个调用都被当做是活跃的。栈上的那块存储空间称为活跃记录(见图2-b),或称为栈帧。栈帧由5个区域组成:输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数。输入参数是传递到活跃记录中的参数;输出参数是传递给在活跃记录中调用的函数所使用的。一个活跃记录中的输出参数就成为栈中下一个活跃记录的输入参数。函数调用所产生的活跃记录将一直存在于栈中直到这个函数调用结束。

  我们以示例fact.c为例,考虑一下当计算4!时栈中都发生了什么(见图3)?初始调用fact会在栈中产生一个活跃记录,输入参数n=4。由于这个调用没有满足函数的终止条件,因此fact将继续以n=3为参数递归调用。这将在栈上创建另一个活跃记录,但这次输入参数n=3。这里,n=3也是第一个活跃期中的输出参数,因为正是在第一个活跃期内调用fact产生了第二个活跃期。这个过程将一直继续,直到n的值变为1,此时满足终止条件,fact将返回1。

  一旦n=1时的活跃期结束,n=2时的递归计算结果就是2X1=2,因而n=2时的活跃期也将结束,返回值为2。结果就是n=3时的递归计算结果表示为3X2=6,因此n=3时的活跃期结束,返回值为6。最终,当n=4时的递归计算结果将表示为6X4=24,n=4时的活跃期将结束,返回值为24。此时,函数已经从最初的调用中返回,递归过程结束。

  栈是用来存储函数调用信息的绝好方案。这正是由于其后进先出的特点精确满足了函数调用和返回的顺序。然而,使用栈也有一些缺点,栈维护了每个函数调用的信息直到函数返回后才释放,这需要占用相当大的空间,尤其是在程序中使用了许多递归调用的情况下。除此之外,因为有大量的信息需要保存和恢复,因此生产和销毁活跃记录需要耗费一定的时间。如此一来,当函数调用的开销变的很大时,我们就需要考虑应该采用迭代的方案。幸运的是,我们可以使用一种称为尾递归的特殊递归方式来避免前面提到的这些缺点。

  如果一上函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。

  当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活跃记录而不是在栈中去创建一个新的。编译器可以做到这一点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。因此, 只要有可能我们就需要将递归函数写成尾递归的形式。

  回忆之前对计算n!的定义:在每个活跃期计算n倍的(n-1)!的值,让n=n-1并持续这个过程直到n=1为止。这种定义不是尾递归的,因为每个活跃期的返回值都依赖于用n乘以下一个活跃期的返回值,因此每次调用产生的栈帧不得不保存在栈上直到下一个子调用的返回值确定。现在让我们考虑以尾递归的形式来定义计算n!的过程。函数可以定义成如下形式:

  这种定义还需要接受第二个参数a,除此以外并没有太大区别。a(初始化为1)维护递归层次的深度。这就避免了每次还需要将返回值再乘以n。而是在每次递归调用中令n=n-1并且a=na。继续递归调用,直到n=1,这满足结束条件,此时直接返回a即可。下图(图4)说明了用尾递归计算4!的过程。注意在回归的过程中不需要做任何的操作,这是所有尾递归函数的标志。

  facttail.c接受一个整数n并以尾递归的形式计算n的阶乘。这个函数还接受一个参数a,a的初始值为1。函数使用a来维护递归层次的深度,除此之外它和fact很相似。

  下面我们来考虑一个使用递归处理反序的问题(在这类问题中使用递归比使用循环更简单)。

  问题是这样的,编写一个函数将一个整数转换成二进制形式。二进制的意思是指数值以2为底数进行表示。

  解决上述问题,需要使用一个算法(algorithm)。因为奇数的二进制形式的最后一位一定是1,而偶数的二进制数的最后一位是0,所以可以通过5%2得出5的进制形式中最后一位数字是1或者是0。一般来讲,对于数值n,其二进制数的最后一位是n%2,因此计算出的第一个数字恰好是需要输出的最后一位。这就需要使用一个递归函数实现。在函数中,首先在递归调用之前计算n%2的数值,然后在递归调用语句之后进行输出,这样计算出的第一个数值反而在最后一个输出。

  如果此时得出的数值是偶数,则下一个二进制数是0;若得出的数值是奇数,则下一个二进制数是1.

  例如,5/2的数值是2(整数除法),所以下一位值是0。这时已经得到了数值01.重复以上计算,即使用2/2得出1,而1%2的数值是1,因此下一位数是1.这时得到的数值是101.那么何时停止这种计算呢?

  因为只要被2除的结果大于或等于2,那么就还需要一位二进制位进行表示,所以只有被2除的结果小于2时才停止计算

  示例程序中,如果r 是0,表达式‘0’+r就是字符‘0’;当r为1时,则该表达式的值为字符‘1’。得出这种结果的前提假设是字符‘1’的数值编码比字符‘0’的数值编码大1.ASCII和EBCDIC两种编码都满足上述条件。更一般的方式,你可以使用如下方法:

  当然,不使用递归也能实现这个算法。但是由于本算法先计算出最后一位的数值,所以在显示结果之前必须对所有的数值进行存储。

  其优点是在于为某些编程问题提供了最简单的方法,而缺点是一些递归算法会很快耗尽内存。同时,使用递归的程序难于阅读和维护。从下面的例子,可以看出递归的优缺点。

  斐波纳契数列定义如下:第一个和第二个数字都是1,而后续的每个数字是前两个数字之和。例如,数列中前几个数字是1,1,2,3,5,8,13.下面我们创建一个函数,它接受一个正整数n作为参数,返回相应的斐波纳契数值。

  首先,关于递归深度,递归提供了一个简单的定义。如果调用函数Fionacci(),当n为1或2时Fabonacci(n)应返回1;对于其他数值应返回Fibonacci(n-1)+Fabonacci(n-2) :

  这个C递归只是讲述了递归的数学定义。同时本函数使用了双重递归(double recursion);也就是说,函数对本身进行了两次调用。这就会导致一个弱点。

  为了具体说明这个弱点,先假设调用函数Fibonacci(40)。第1级递归会创建变量n。接着它两次调用Fibonacci(),在第2级递归中又创建两个变量n。上述的两次调用中的每一次又进行了再次调用,因而在第3级调用中需要4个变量n,这时变量总数为7.因为每级调用需要的变量数是上级的两倍,所以变量的个数是以指数规律增长的!这种情况下,指数增长的变量数会占用大量内存,这就可能导致程序瘫痪。当然,以上是一个比较极端的例子,但它也表明了必须小心使用递归,尤其效率处于第一位时。

  递归树:画图表能帮助我们形象地理解函数的调用顺序。递归树在形式上有所不同,展示递归计算阶乘的图1和图4都是递归树。递归树最常用在包含两个或更多个递归调用的函数中。

  首页最新文章在线课程业界开发IT技术设计创业IT职场在国外频道更多伯乐在线首页所有文章C/C++递归与尾递归(C语言)递归与尾递归(C语言)2014/12/05分类:C/C++,IT技术...博文来自:钱国正的专栏

  什么是尾调用在计算机科学里,尾调用是指一个函数里的最后一个动作是一个函数调用的情形,即这个调用的返回值直接被当前函数返回的情形。这种情形下称该调用位置称为“尾位置”。说得通俗点,尾调用就是指某个函数的...博文来自:车子(chezi)

  昨天被问到了尾递归及编译器对它的处理相关,一直对它没有研究过,解释得很含糊。回来查了下,记录如下:递归有线性递归(普通的递归)和尾递归。由于尾递归的特殊性,一般的编译器会做些特殊处理。因此,在效率和开...博文来自:Kayven@数据

  函数的递归调用:一个函数在它的函数体内,直接或者间接地调用了他本身。直接递归调用:函数直接调用自身。                             间接递归调用:函数间接调用自身。如下图: ...博文来自:like_that的博客

  一、基本概念:c语言通过运行时堆栈来支持递归的实现的。递归函数就是直接或者间接调用自身的函数。这里有一个简单的程序,可用来说明递归。程序的目的是将一个整数从二进制形式转化为可打印的字符形式,例如给出一...博文来自:flowing_wind的博客

  1.接受一个整形值(无符号),把它转换为字符并打印它模拟实现strlen()函数。3.求n的阶乘4.斐波那契数列总结1.接受一个整形值(无符号),把它转换为字符并打印它voidfun(intx){if...博文来自:csdn_kou的博客

  c语言可以将代码模块化,这是其很重要的一个特性。说道代码模块化,我们很自然的就会联想到函数。而函数中,比较难的一个知识点就是函数的递归调用。值得注意的是,函数的递归调用在现实工作并不是很常用,但是涉及...博文来自:最高权限比特流

  递归调用,简而言之就是函数调用自身。执行递归函数将反复调用其自身,每调用一次就进入新的一层。递归的原理比较简单,但是想要合理并且高效的应用起来不是那么容易,因为它的思想比较难,而且稍微控制不好,便会导...博文来自:Xiaogang LI的博客

  1.递归算法递归算法:是一种直接或者间接地调用自身的算法。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。递归过程一般通过函数或子过程来实现。递归算法的实...博文来自:weixin_42145502的博客

  #include/*快速排序描述:1.从数列中挑出一个元素,称为基准(pid)2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这...博文

  递归的定义:程序调用自身的编程技巧称为递归,就是运行时调用了自己。什么样的问题适合使用递归方式:如果一个大问题可以拆分成几个小问题,其中有n个小问题和原来的大问题本质一样,只是难度小一些。这种问题可以...博文来自:u013171437的博客

  1.定义:在调用一个函数的过程中又出现直接或间接调用该函数本身,博文来自:RamiYim的专栏

  啥是递归?即是该函数调用它本身自己,这种调用过程称为递归。递归可以相当于循环,所以想结束递归,就必须有终止递归的条件测试部分,否则就会出现无限递归(即无限循环)。同时,这也是使用递归的难点。...博文来自:CSDN_zhi的博客

  最近在学数据结构的二叉树,里面的实现好多都是递归。博主大一上学期也没有认真学递归,结果就好多不懂。今天特别请教了班上搞ACM的,再上网猜了一些资料才算初步弄懂递归的实现原理。递归的底层实现其实是栈,而...博文来自:Hitmi_的博客

  一个函数在函数体内调用自己,就被称作递归调用,也即函数直接或间接地调用函数自身。函数的递归调用时一种很有用的编程技巧。有时可以使用递归来实现循环。对于某些问题,用递归的思路来解决问题,可以让问题更加清...博文来自:str999_cn的专栏

  原网址:一、基本内容:C语言中的函数可以递归调用,即:可以直接(简单递归)或间接(间接递归)地自己调自己。要点:1...博文来自:LOI_Q的博客

  1.问题描述:写一个递归函数DigitSum(n),输入一个非负整数,返回组成它的数字之和。例如,调用DigitSum(1729),则应该返回1+7+2+9,它的和是19。思路:这个题比较类似于求拆分...博文来自:Monster_Girl

  C语言中,所有的执行语句都只能出现在函数之中。同样,函数的调用也只能出现在某函数的函数体内。函数的调用以两种方式出现:函数的嵌套与函数的递归。C语言中,所有函数的定义都是互相平行和独立的,一个函数...博文来自:iwm_NeXT的专栏

  递归:”递:传递,“归”:回归。简单的解释:方法内调用它本身。传递和回归必须存在一个临界点:比如最内层被调用的方法内给了一个返回值,或者是最内存被调用方法结束,然后将结果返回给上一层的方法.,然后一...博文来自:ITdevil的博客

  1、计算机与程序设计的关系计算机的本质是程序的机器,程序和指令是计算机系统中最基本的概念。程序语言设计的产生是为了克服繁琐难记的二进制语言代码。2.C语言程序的特点优点:①语言简洁、紧凑;使用方便,灵...博文来自:wxycheng的博客

  前言栈帧也叫过程活动记录,是编译器用来实现函数调用过程的一种数据结构。C语言中,每个栈帧对应着一个未运行完的函数。从逻辑上讲,栈帧就是一个函数执行的环境:函数调用框架、函数参数、函数的局部变量、函数执...博文来自:栓鸣博客

  本文主要从进程栈空间的层面复习一下C语言中函数调用的具体过程,以加深对一些基础知识的理解。先看一个最简单的程序:点击(此处)折叠或打开/*test.c*/ #includestdio.h>...博文来自:Commander

  第三章  递归1  递归大佬说:“如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。”2  基线条件和递归条件每个递...博文来自:的博客

  本文主要介绍了递归算法以及它的优化,并介绍了栈(Stack)的特性。博文来自:xiaodianzichen的专栏

  学习PHP是一个慢慢积累和理解的过程,只有理解才能完整记忆,才能更好的拓展知识点,整合知识点,做出更强大的WEB程序。今天在这里用图解和言简意赅的描述方式帮助大家理解一下第一阶段的一个难点,递归函数。...博文来自:兄弟连_战地日记

  最近在学习机器学习算法中的决策树算法,其中在建树的过程中用到了递归调用的思想,于是在这里复习一下递归调用的一些知识。下面test1函数是转自“深入理解递归函数的调用过程”这篇博客,后面两个函数是我根据...博文来自:笑着流浪的博客

  在传统的递归中,典型的模型是首先执行递归调用,然后获取递归调用的返回值并计算结果。以这种方式,在每次递归调用返回之前,您不会得到计算结果。在尾递归中,首先执行计算,然后执行递归调用,将当前步骤的结果传...博文来自:Vermont_的博客

  作者:Coke链接:来源:知乎著作权归作者所有,转载请联系作者获得授权。这是尾递归:intf...博文来自:shuoGG的专栏

  递归与递归函数递归:是C语言编程中,分析复杂问题的重要思想。递归函数:是指一个函数的函数体中直接或间接调用了该函数自身。 递归函数执行过程递推阶段:从原问题出发,按递归公式递推从未知到已知,最终达到递...博文来自:本末实验室

  一、什么叫做递归?一个过程或 函数 在其定义或说明中有直接或间接调用自身的一种方法;递归函数就是直接或间接调用自身的函数,也就是自身调用自己;刚接触递归的同学,可能难以理解递归,难以理解的点可能很多,...博文来自:的博客

  jquery/js实现一个网页同时调用多个倒计时(最新的)nn最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦!nnnn//jsn...博文来自:Websites

本文链接:http://windsorflowers.net/diguilicheng/315.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部