递归函数的返回值问题

返回值问题
有一些经典的数学问题，使用递归函数来解决都非常方便。阶乘就是这样一个典型的问题，清单 5 给出了一个实现阶乘计算的bash脚本(当然，除了使用递归函数之外，简单地利用一个循环也可以实现计算阶乘的目的，不过本文以此为例来介绍递归函数的相关问题)。

清单5. 阶乘函数的bash实现
               
[root@localhost shell]# cat -n factorial1.sh

     1 #!/bin/bash

     2
     3 factorial()
     4 {
     5 i=$1
     6
     7 if [ $i -eq 0 ]
     8 then
     9 return 1;
    10 else
    11 factorial `expr $i - 1`
    12 return `expr $i \* $? `
    13 fi
    14 }
    15
    16 if [ -z $1 ]
    17 then
    18 echo "Need one parameter."
    19 exit 1
    20 fi
    21
    22 factorial $1
    23
    24 echo $?
[root@localhost shell]# ./factorial1.sh 5

0
 
这个脚本看上去并没有什么问题：递归函数的参数传递和普通函数没什么不同，返回值是通过获取 $? 的值实现的，这是利用了执行命令的退出码。然而，最终的结果却显然是错误的。调试一下就会发现，当递归回溯到尽头时，变量 i 的值被修改为 0；而退出上次函数调用之后，变量 i 的新值也被带了回来，详细信息如清单 6 所示。

清单6. 调试 factorial1.sh 的问题
               
[root@localhost shell]# export PS4='+[$FUNCNAME: $LINENO] '

[root@localhost shell]# sh -x factorial1.sh 5

+[: 16] '[' -z 5 ']'
+[: 22] factorial 5
+[factorial: 5] i=5
+[factorial: 7] '[' 5 -eq 0 ']'
++[factorial: 11] expr 5 - 1
+[factorial: 11] factorial 4
+[factorial: 5] i=4
+[factorial: 7] '[' 4 -eq 0 ']'
++[factorial: 11] expr 4 - 1
+[factorial: 11] factorial 3
+[factorial: 5] i=3
+[factorial: 7] '[' 3 -eq 0 ']'
++[factorial: 11] expr 3 - 1
+[factorial: 11] factorial 2
+[factorial: 5] i=2
+[factorial: 7] '[' 2 -eq 0 ']'
++[factorial: 11] expr 2 - 1
+[factorial: 11] factorial 1
+[factorial: 5] i=1
+[factorial: 7] '[' 1 -eq 0 ']'
++[factorial: 11] expr 1 - 1
+[factorial: 11] factorial 0
+[factorial: 5] i=0
+[factorial: 7] '[' 0 -eq 0 ']'
+[factorial: 9] return 1
++[factorial: 12] expr 0 '*' 1
+[factorial: 12] return 0
++[factorial: 12] expr 0 '*' 0
+[factorial: 12] return 0
++[factorial: 12] expr 0 '*' 0
+[factorial: 12] return 0
++[factorial: 12] expr 0 '*' 0
+[factorial: 12] return 0
++[factorial: 12] expr 0 '*' 0
+[factorial: 12] return 0
+[: 24] echo 0
0
 
这段脚本问题的根源在于变量的作用域：在shell脚本中，不管是否在函数中定义，变量默认就是全局的，一旦定义之后，对于此后执行的命令全部可见。 bash也支持局部变量，不过需要使用local关键字进行显式地声明。local 是bash中的一个内嵌命令，其作用是将变量的作用域设定为只有对本函数及其子进程可见。局部变量只能在变量声明的代码块中可见，这也就意味着在函数内声明的局部变量只能在函数代码块中才能被访问，它们并不会污染同名全局变量。因此为了解决上面这个程序的问题，我们应该使用local关键字将i声明为局部变量。修改后的脚本如清单7所示。

清单7. 递归函数中使用local关键字声明局部变量
               
[root@localhost shell]# cat -n factorial2.sh

     1 #!/bin/bash

     2
     3 factorial()
     4 {
     5 local i=$1
     6
     7 if [ $i -eq 0 ]
     8 then
     9 return 1;
    10 else
    11 factorial `expr $i - 1`
    12 return `expr $i \* $? `
    13 fi
    14 }
    15
    16 if [ -z $1 ]
    17 then
    18 echo "Need one parameter."
    19 exit 1
    20 fi
    21
    22 factorial $1
    23
    24 echo $?
[root@localhost shell]# ./factorial2.sh 5

120
[root@localhost shell]# ./factorial2.sh 6

208
            
这下 5 的阶乘计算对了，但是稍微大一点的数字都会出错，比如 6 的阶乘计算出来是错误的 208。这个问题的原因在于脚本中传递函数返回值的方式存在缺陷，$? 所能传递的最大值是 255，超过该值就没有办法利用这种方式来传递返回值了。解决这个问题的方法有两种，一种是利用全局变量，另外一种则是利用其他方式进行周转(例如标准输入输出设备)。清单 8 和清单 9 分别给出了这两种方法的参考实现。

清单8. 使用全局变量传递返回值
               
[root@localhost shell]# cat -n factorial3.sh

     1 #!/bin/bash

     2
     3 factorial()
     4 {
     5 local i=$1
     6
     7 if [ $i -eq 0 ]
     8 then
     9 rtn=1
    10 else
    11 factorial `expr $i - 1`
    12 rtn=`expr $i \* $rtn `
    13 fi
    14
    15 return $rtn
    16 }
    17
    18 if [ -z $1 ]
    19 then
    20 echo "Need one parameter."
    21 exit 1
    22 fi
    23
    24 factorial $1
    25
    26 echo $rtn
[root@localhost shell]# ./factorial3.sh 6

720
 

清单9. 利用标准输入输出设备传递返回值
               
[root@localhost shell]# cat -n factorial4.sh

     1 #!/bin/bash

     2
     3 factorial()
     4 {
     5 local i=$1
     6
     7 if [ $i -eq 0 ]
     8 then
     9 echo 1
    10 else
    11 local j=`expr $i - 1`
    12 local k=`factorial $j`
    13 echo `expr $i \* $k `
    14 fi
    15 }
    16
    17 if [ -z $1 ]
    18 then
    19 echo "Need one parameter."
    20 exit 1
    21 fi
    22
    23 rtn=`factorial $1`
    24 echo $rtn
[root@localhost shell]# ./factorial4.sh 6

720
 
尽管利用全局变量或标准输入输出设备都可以解决如何正确传递返回值的问题，但是它们却各有缺点：如果利用全局变量，由于全局变量对此后的程序全部可见，一旦被其他程序修改，就会出错，所以编写代码时需要格外小心，特别是在编写复杂的递归程序的时候；如果利用标准输入输出设备，那么递归函数中就存在诸多限制，例如任何地方都不能再向标准输出设备中打印内容，否则就可能被上一层调用当作正常输出结果读走了，另外速度方面也可能存在严重问题。

 原文地址 http://www.bsdlover.cn/html/53/n-453.html