黑马程序员技术交流社区

标题: 【笔记】头脑风暴中的递归树分析 [打印本页]

作者: 倾心莫若初见 时间: 2016-10-31 13:30
标题: 【笔记】头脑风暴中的递归树分析
本帖最后由倾心莫若初见于 2016-10-31 13:34 编辑

头脑风暴中的递归树分析

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

习题代码如下：

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

显然函数执行的代码应该是 f1=fn(6 - 1); 即 f1=fn(5); 此时又进入fn（5）的内部，代码变为：

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

上述压栈过程化成图像如下所示：

当执行fn(2)函数时，显然函数返回值为1，返回给fn（3）函数内部的局部变量f1=1;此时fn(2)出栈，变为如下图：

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

Fn(1)函数会给fn（3）内部的局部变量f2返回值1,即f2=1;此时程序示意图变为：

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

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

此时函数fn（6）执行return f1+f2; 返回值为8;main函数的打印值也就为8；上述过程还可以画二叉树的形式表示，如下：

其中红线表示压栈过程，绿线表示出栈过程。同学们好好分析一下，这样就会对递归以及函数的压栈出栈理解的更深一步了。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2