bash 中的递归斐波那契函数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19624278/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
A recursive fibonacci function in bash
提问by misterbreadcrum
I was perusing the sight for some help with my code and came across a thread from about 4 months ago, however the user's final revision doesn't work when posted into bash, and produces some strange results. Here is my version, which also produces some strange results:
我正在仔细阅读有关代码的一些帮助，并在大约 4 个月前遇到了一个线程，但是用户的最终修订在发布到 bash 时不起作用，并产生了一些奇怪的结果。这是我的版本，它也产生了一些奇怪的结果：
#!/bin/bash
fib()
{
ind=
if (( ind <= 0 ))
then echo 0
elif (( ind = 1 ))
then echo 1
else
echo $(( $(fib $((ind - 1)) ) + $(fib $((ind - 2)) ) ))
fi
}
echo fibbonacci sequence number is $(fib )
so this block of code will end up alwaysoutputting 1. ./fib.sh 5 outputs fibbonacci sequence number 5 is 1
所以这段代码最终总是输出 1../fib.sh 5 输出斐波那契序列号 5 是 1
so I tried to write the code a little closer to what the previous asker had,
所以我试着把代码写得更接近上一个提问者的代码，
#!/bin/bash
fib()
{
ind=
if (( ind <= 0 ))
then echo 1
else
echo $(( $(fib $((ind - 1)) ) + $(fib $((ind - 2)) ) ))
fi
}
echo fibbonacci sequence number is $(fib )
While I don't understand the logic here, it actually starts to output fibonacci numbers, but now I get a slightly different problem; ./fib.sh 3 outputs: fibbonacci sequence number 3 is 5 ./fib.sh 5 outputs : fibbonacci sequence number 5 is 13 Well we know that the 3rd fibonacci number is 1, and the 5th is 3 so what gives? The code seems to skip ahead several fibonacci numbers, and I can't figure out what is logically wrong with my code.
虽然我不明白这里的逻辑，但它实际上开始输出斐波那契数，但现在我遇到了一个稍微不同的问题；./fib.sh 3 输出：fibbonacci 序列号 3 是 5 ./fib.sh 5 输出：fibbonacci 序列号 5 是 13 我们知道第 3 个斐波那契数是 1，第 5 个是 3 那么是什么？代码似乎跳过了几个斐波那契数字，我无法弄清楚我的代码在逻辑上有什么问题。
回答by Christian Ternus
Usually when writing Fibonacci sequence logic you have to special-case the first two numbers. That's what the first user has done: special-casing 0 and 1.
通常在编写斐波那契数列逻辑时，您必须对前两个数字进行特殊处理。这就是第一个用户所做的：特殊外壳 0 和 1。
You've removed one instance of special-casing and shifted everything by one index, which explains one shift. The other is easy: the code is zero-indexed. That's why everything is "off by two".
您已经删除了一个特殊大小写的实例并将所有内容都移动了一个索引，这解释了一次移动。另一个很简单：代码是零索引的。这就是为什么一切都是“两个”的原因。
What's wrong with the original code? This line:
原来的代码有什么问题？这一行：
elif ((ind = 1))
setsind to 1. Otherwise it's fine.
将ind设置为 1。否则没关系。
A simple fix to your code is to replace this line:
对您的代码的一个简单修复是替换此行：
if (( ind <= 0 ))
with
和
if (( ind <= 2 ))
and off you go. That gives you the one-indexed behavior you'd expect:
你走吧。这为您提供了您期望的单索引行为：
cternus@astarael ~/foo> for i in `seq 1 10`; do ./foo.sh $i; done
fibbonacci sequence number 1 is 1
fibbonacci sequence number 2 is 1
fibbonacci sequence number 3 is 2
fibbonacci sequence number 4 is 3
fibbonacci sequence number 5 is 5
fibbonacci sequence number 6 is 8
fibbonacci sequence number 7 is 13
fibbonacci sequence number 8 is 21
fibbonacci sequence number 9 is 34
fibbonacci sequence number 10 is 55
回答by Andrii Kovalchuk
#!/bin/bash
function fib(){
if [ -le 0 ]; then
echo 0
elif [ -eq 1 ]; then
echo 1
else
echo $[`fib $[-2]` + `fib $[ - 1]` ]
fi
}
fib
回答by misterbreadcrum
#!/bin/bash
#fibonacci sequence function
fib()
{
ind=
if (( ind <= 0 ))
then echo 0
elif (( ind == 2 ))
then echo 1
else
echo $(( $(fib $((ind - 1)) ) + $(fib $((ind - 2)) ) ))
fi
}
echo fibbonacci sequence number is $(fib )
So my problem was with the equality check in
所以我的问题是平等检查
elif (( ind = 1 ))
I should have used the double =, and change the 1 to a 2, so it should have been
我应该使用双 =，并将 1 更改为 2，所以它应该是
elif (( ind == 2 ))
Ultimately my correct script should look like this
最终我的正确脚本应该是这样的
#!/bin/bash
#fibonacci sequence function
fib()
{
ind=
if (( ind <= 1 ))
then echo 0
elif (( ind == 2 ))
then echo 1
else
echo $(( $(fib $((ind - 1)) ) + $(fib $((ind - 2)) ) ))
fi
}
echo fibbonacci sequence number is $(fib )
Thanks a bajillion and one to Christian Ternus for the help, I've been programming for a few years now and totally should have seen the equality check error >.<
感谢 bajillion 和 Christian Ternus 的帮助，我已经编程几年了，完全应该看到平等检查错误>。<
回答by ckujau
Interestingly enough, the Korn shell executes @christianternus' script much faster than other shells:
有趣的是，Korn shell 执行 @christianternus 的脚本比其他 shell 快得多：
$ for a in sh bash zsh ksh; do echo "shell: $a"; time for i in $(seq 1 20); do $a bin/fib.sh $i; done | md5sum; done shell: sh 5fece53a38f2df040bfaf9632c2b7f4b - real 0m29.508s user 0m3.788s sys 0m11.785s shell: bash 5fece53a38f2df040bfaf9632c2b7f4b - real 0m29.906s user 0m3.604s sys 0m11.235s shell: zsh 5fece53a38f2df040bfaf9632c2b7f4b - real 0m29.203s user 0m2.505s sys 0m14.377s shell: ksh 5fece53a38f2df040bfaf9632c2b7f4b - real 0m0.942s user 0m0.843s sys 0m0.079s
