bash - 生成斐波那契数列的 Shell 脚本

Question

我正在尝试创建一个递归函数来计算斐波那契数列中的第 n 个数。我已经找到了很多解决这个问题的方法，但我不知道为什么我的方法不起作用。谢谢。

function fib ()
{
        if [ $1 -eq 1 -o $1 -eq 2 ]
        then
                return 1
        else
               let nr=$1-1
               fib $nr
               rez1=$?
               let nr=$1-2
               fib $nr
               rez2=$?
               let rez=$rez1+$rez2
               return $rez
        fi
}

Answer 1

这里有两个问题。首先，您所有的变量都是全局变量，这意味着当您进行递归调用时，它会覆盖 nr、rez、rez1、和 rez2。您可以通过将它们声明为 local 来解决此问题:

fib() {
    local nr rez rez1 rez2
    if [ $1 -eq 1 -o $1 -eq 2 ]; then
        return 1
    else
        let nr=$1-1
        fib $nr
        rez1=$?
        let nr=$1-2
        fib $nr
        rez2=$?
        let rez=$rez1+$rez2
        return $rez
    fi
}

第二个问题是您试图通过函数的返回状态传递一个数字。返回状态是一个 1 字节的无符号整数，这意味着它不能大于 255(之后返回到 0。它的真正目的是给出成功/失败的结果(可能还有一些关于失败的信息)， 0 表示成功，其他任何表示错误。尝试将其用于其他用途是自找麻烦。您可以在此处查看结果(来自函数的本地化版本):

$ fib 11; echo $?
89
$ fib 12; echo $?
144
$ fib 13; echo $?
233
$ fib 14; echo $?
121

第 14 个斐波那契数是 377，但它超过了 255，所以结果是 377-256 = 121。要解决这个问题，通过 echo 将结果返回到标准输出并用 $( ):

fib() { 
    local nr rez rez1 rez2
    if [ $1 -eq 1 -o $1 -eq 2 ]; then
        echo 1
    else
        let nr=$1-1
        rez1=$(fib $nr)
        let nr=$1-2
        rez2=$(fib $nr)
        let rez=$rez1+$rez2
        echo $rez
    fi
}

...不过，这确实有一个缺点:速度要慢得多，因为对 fib 的每次调用都必须作为子进程运行，而创建子进程的计算成本很高。 (这实际上已经解决了全局变量问题，因为变量向下继承到子进程而不是从它们向上继承；但它只是偶然地解决了它。)

重要教训:shell 脚本不是处理这类事情的正确语言。