学习网

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 39391|回复: 0
收起左侧

高级语言程序设计 - 吉林大学-9.3.1 递归程序设计

[复制链接]
发表于 1-26 01:41 | 显示全部楼层 |阅读模式
下面我们开始学习递归程序设计这一章主要理解递归的思想我们先从一个例题开始编一个函数求n的阶乘n的阶乘是啥呢1乘2乘3一直乘到n大家都知道这个程序咱们都编过了按照一般的过去的程序设计思想这个函数应该这么编一个编程级1乘到n很简单但是现在换一个角度来想问题这个n的阶乘啊不仅仅是1乘2乘3一直到n还可以这么定义当n等于零的时候n的阶乘值就是1当n不等于零的时候n的阶乘是n乘n减一的阶乘没问题吧按照这个定义来讲如果我们写程序 怎么写这就是一个分支分支和表达式计算没有什么循环不循环的那么程序就可以写出来这样似的if n 等于零 return1否则返回n乘(n-1)的阶乘n阶乘的函数写成这样现在问题来了这样写程序对不对在这个一个函数内部又调用着函数本身行不行 存在这样一个问题回答是肯定的 行为什么说行呢 从作用域的规则来讲调用这个n的阶乘函数这个地方在他作用域之内阶乘函数它的作用域是它的定义点的开始往下到整个程序文本结束所以他这块的作用之内它是合理的 所以是合法的第二点呢也很重要C系统保证程序这么编是正确的其他有些系统是不能保证这点的比如说factorrial语言 你要这么写程序执行不正确 肯定是不对的C系统能保证这个程序执行正确这就是递归咱们再分析一下看从程序的静态行文上看在定义这个函数的时候这个函数内部又对他本身进行调用这个呢就叫做递归这个函数就是递归定义的如果从动态执行角度来看呢当调用一个函数进去了 还没退出之前又再一次的调用这个函数又进去了这种情况就称作递归或者称为这对个函数的递归调用像求阶乘的函数一样它是一个递归定义的咱们就称递归定义的函数为递归函数下面咱们执行一下这个程序执行输入一个n比如输入5 求5的集成得120 对吧这程序执行是正确的这个程序是怎么执行的呢咱们看一看 那个机器内部执行一下过去 咱也看不到里边怎么执行的咱们模拟的手工的执行一下这个程序看一看咱们看一下它的计算过程首先从主函数开始执行要打印 打印呢要调用f函数求阶乘的函数 f5 要调用调用函数呢进入函数里面他执行什么n得5啊执行后面 返回n乘以n-1的阶乘那也就是五乘以四的阶乘执行这个执行这条吧执行这条要返回要返回计算表达式值得先计算s4计算4的阶乘计算4的阶乘怎么办调用求阶乘函数调用求阶乘函数里又执行返回n乘(n-1)阶乘n是4 (n-1)是3就是返回4乘以3的阶乘要返回这个值 得先计算这个表达式的值计算表达式的值 得计算3的阶乘那就调用求阶乘函数f3进去之后 进到求阶乘函数之后又执行的是返回n乘以n-1的阶乘又执行这一行执行这行要返回一个值计算后面表达式的值这个表达式要调用求阶乘函数计算2的阶乘计算2的阶乘 进来之后又是返回n乘以n-1的阶乘那么这是2乘1的阶乘计算这个表达式 带到表达式返回要计算这个表达式呢 又得求f1计算1的阶乘计算1的阶乘进入到函数里之后返回 因为n不等于0么返回n乘(n-1)的阶乘返回1乘以0的阶乘带着这个表达式值返回这个表达式值要计算你的计算0的阶乘又一次调用求阶乘函数计算f0计算f0进来之后n等于0了返回1返回1返回到哪去返回到刚才调用的地方计算f0那块 返回到这咱在下面这块呢是一趟的抻开了实际上返回的位置就是函数里面那个调用(n-1)的阶乘那个位置就是那个地方返回到那f0得1了那么1乘以1得1这个表达式算出来了可以带着1的值返回返回到哪从程序上看还是返回到n-1的位置咱们这里图都分解开了返回到哪里返回到f1那块f1得1了那2乘以1得2返回2这个返回 返回2返回到哪里去计算2的阶乘那个位置从程序上看还是求n-1阶乘的那个位置返回到那现在呢f2得2了表达式就算出来了返回啥3乘2得6 返回6带着6值返回 返回到哪还是返回到n-1阶乘那从底下这个图上分解来看呢 返回到f3这现在f3得6 4乘6得24可以带着24位值返回了返回到哪还是返回到求n-1的阶乘那块在这个分解这 返回到求4的阶乘这那5乘24算出来了得120返回返回到哪里 这回返回到printf打印里面的f5那块 返回到那f5算出来了得120那打印120 这个程序就执行完了咱们模拟的看一下递归函数的执行过程也就是说求阶乘的这个函数它的执行过程从这里面大家可以进一步理解递归是怎么回事计入函数了然后呢在这函数里又调用它本身每次调用它本身都有新的运算就是这样一个过程有关递归的引进咱们就介绍到这[此为课程内容大纲,相关资源下载地址请在论坛搜索标题名称]

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|小黑屋|学习资源网 ( 粤ICP备16100991号-2 )

GMT+8, 12-5 08:06 , Processed in 0.179348 second(s), 31 queries .

Powered by Discuz! X3.4 Licensed

© 2001-2017 Comsenz Inc. Template By ¡¾Î´À´¿Æ¼¼¡¿¡¾ www.wekei.cn ¡¿

快速回复 返回顶部 返回列表