传智播客旗下技术交流社区北京校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 倾心莫若初见 于 2016-10-31 13:34 编辑

头脑风暴中的递归树分析
好多同学在学习递归时,一时陷于头脑风暴之中,不清楚到底是怎么回事,往往脑袋的内存用尽了,还是没有厘清思路。下面通过一个递归树的习题,我从几个角度分析,帮助大家理解递归函数的运行过程。
习题代码如下:
1.jpg



    要解决这个问题,我们需要从main函数开始分析,当变量num作为参数调用fn函数时,此时内存先压栈fn6)函数,进入fn(6)内部时,代码变为:
2.jpg



  显然函数执行的代码应该是 f1=fn(6 - 1); 即 f1=fn(5); 此时又进入fn5)的内部,代码变为:
3.jpg



  一次类推直至函数进入 f1=fn(3- 1),即fn(2);此时代码为:

4.jpg



   上述压栈过程化成图像如下所示:
5.jpg




   当执行fn(2)函数时,显然函数返回值为1,返回给fn3)函数内部的局部变量f1=1;此时fn(2)出栈,变为如下图:
6.jpg




   然后又进入fn(3)内部的代码f2=fn(3- 2);即f2=fn(1),再次压栈过程如下:
7.jpg



Fn(1)函数会给fn3)内部的局部变量f2返回值1,f2=1;此时程序示意图变为:
8.jpg


  此时泛函fn(3)执行的语句是return f1+f2;显然fn4)内部的局部变量f1=2;示意图如下:

9.jpg


  此时fn4)函数继续执行的代码变为 f2=fn4-2),即f2=fn(2);按照上述过程分析可以此类推至fn6)内部的局部变量f1=5f2= 3;示意图如下:

10.jpg


  此时函数fn6)执行return f1+f2; 返回值为8;main函数的打印值也就为8;上述过程还可以画二叉树的形式表示,如下:
11.jpg
     其中红线表示压栈过程,绿线表示出栈过程。同学们好好分析一下,这样就会对递归以及函数的压栈出栈理解的更深一步了。
12.jpg

精华推荐:
3分钟带你读懂C/C++学习路线
为什么来黑马程序员学C/C++? 稳做IT贵族人才!
2016最新C++学习路线图(附完整视频资源)+ 笔记 + 工具 + 面试题总结!
分享至 : QQ空间
收藏

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马
关闭

站长推荐 上一条 /4 下一条