Chinaunix

标题: 新人学习递归函数求助 [打印本页]

作者: yzxarlen 时间: 2013-07-30 17:53
标题: 新人学习递归函数求助
小弟在一本书上看到一个数学阶乘的范例，一直不解。我先把脚本贴上来。

function factor_in()  {
local tmp
local tmp1

tmp="$1"

if [ $tmp -eq 1 ] ;then
echo -n " 1 "
r=1

else

echo -n " $tmp * "
tmp1=$tmp
tmp=$(($tmp-1))
factor_in $tmp
#计算总乘积
r=$(($tmp1 * $r))

fi
}

echo
echo -n $1 " ! = "
factor_in $1
echo -n "= $r"
echo

这段脚本还有个判断提供的参数是否正确，我就不敲了。

小弟我不太理解标红的那段代码。先从if 那里开始：（假设$1 是 5）

1. r 开始是没有值的，除非$tmp 等于 1，才会赋予 r 的值为1 ，这么理解对吗？

2. 否则，开始执行else后面的命令， r=$(($tmp1 * $r)) 也是属于 else 后面的命令，对吗？

3. 既然执行else后面的命令，这个时候 r 是没有值的，但小弟把 r=$(($tmp1 * $r))  改为   echo "$tmp1 * $r" ，发现显示的是
2 * 1
3 * 1
4 * 1
5 * 1

问题1：r是没有值的，为什么会显示后面的 1，而且把r 改为 2 ，显示的结果也都是 * 2。

问题2：r=$(($tmp1 * $r))  是怎么在循环中计算总乘积的。

还请路过的各位大哥帮忙解答下，谢谢。

作者: spiraspera 时间: 2013-07-30 18:09
在运行r=$(($tmp1 * $r))之前，他必须先运行factor_in $tmp
这边就是运用递归
假如$1是5，他先运行factor_in $tmp，此时$tmp是4，进行递归，
此时$1变成4，再运行factor_in $tmp，此时$tmp是3，
以此类推，当$tmp为1时，if [ $tmp -eq 1 ] 判断成立，给r赋值为1。此时最里层的factor_in 方法运行结束，
跳到外面一层，继续运行r=$(($tmp1 * $r))，即 r=2*1，此时factor_in 方法又结束，
跳到再外面一层，继续运行r=$(($tmp1 * $r)),
直到最后方法运行结束。

不知道这么说清楚么

作者: yzxarlen 时间: 2013-07-31 11:07
回复 2# spiraspera
谢谢，差不多理解了，问了些其他人，貌似是 else 后面的递归完后，再回到 else之前，赋值r=1 。然后 if 语句结束。

作者: cao627 时间: 2013-07-31 13:03
@yzxarlen程序书写出来，那些语句前后左右永远是平面关系，但要理解的要有纵向思维，特别是递归。

多多练习，想想下面一个问题的求解过程：

一个盒子，体积不知道，只知道里面嵌套多层盒子，且最里面的盒子（该盒子里不再有盒子）的体积是a
其他每层的盒子都是其里面的那个盒子的体积加一个固定常数n。

现在求最外层的盒子的体积。

作者: jason680 时间: 2013-07-31 13:48
回复 3# yzxarlen

you have to know the recursion

f(n) = f(n-1) * n
f(1) = 1

1. f(5)
you can't get the result for f(5)
call f(4) * 5
2. f(4)
you can't get the result for f(4)
call f(3) * 4
...
3. f(3)
you can't get the result for f(3)
call f(2) * 3
...
4. f(2)
you can't get the result for f(2)
call f(1) * 2

5. f(1)
Now, you can get the result 1 for f(1)
use global r variable return the value 1

6. f(2) get result 2 by f(1) * 2

7. f(3) get result 6 by f(2) * 3

8. f(4) get result 24 by f(3) * 4

8. f(5) get result 120 by f(4) * 5

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)