bash - Bash 脚本中的递归斐波那契

Question

这是我的尝试：

#!/bin/bash

function fibonacci(){

first=$1
second=$2

if (( first <= second ))
then
return 1

else 

return $(fibonacci $((first-1)) ) + $(fibonacci $((second-2)) )
fi
}

echo $(fibonacci 2 0)

我认为我在使用 else 语句时遇到了问题。我得到错误return: +: numeric argument required 。

我遇到的另一个问题是脚本不显示任何数字，即使我这样做了echo $(fibonacci 0 2)。我认为它会显示 1，因为在这种情况下我会返回 1。有人可以给我一些关于如何做到这一点的提示吗？

在检查了你的一些答案之后，这是我的第二次尝试。它可以正常工作，只是它以 1+1+1+1 等形式显示第 n 个斐波那契数。有什么想法吗？

#!/bin/bash

function fibonacci(){

first=$1
second=$2

if (( first <= second ))
then
echo 1


else 

echo $(fibonacci $((first-1)) ) + $(fibonacci $((first-2)) )
fi
}

val=$(fibonacci 3 0)
echo $val

我的最后尝试：

#!/bin/bash

function fibonacci(){

first=$1

if (( first <= 0 ))
then
echo 1


else 

echo $(( $(fibonacci $((first-1)) ) + $(fibonacci $((first-2)) ) ))
fi
}

val=$(fibonacci 5)
echo $val

谢谢伙计们。

Answer 1

#!/bin/bash

function fib(){
    if [ $1 -le 0 ]; then
        echo 0
    elif [ $1 -eq 1 ]; then
        echo 1
    else
        echo $[`fib $[$1-2]` + `fib $[$1 - 1]` ]
    fi

}

fib $1

Answer 2

替换运算符将$(...)替换为命令的输出。您的函数不会产生任何输出，$(...)空字符串也是如此。

函数的返回值$?就像外部命令的退出代码一样。

因此，您需要产生一些输出（使函数回显其结果而不是返回它）或$?在每次调用后使用以获取值。我会选择回声。

Answer 3

正如 Wumpus 所说，您需要使用例如产生输出echo。但是，您还需要修复递归调用。最外面的操作将是一个加法，那就是你想要的：

echo $(( a + b ))

a和都是b的替代品fibonacci，所以

echo $(( $(fibonacci x) + $(fibonacci y) ))

x又y是算术表达式，所以每个都需要自己的$(( ))，给出：

echo $(( $(fibonacci $((first-1)) ) + $(fibonacci $((second-2)) ) ))

如果您对此感到困惑，您应该将组件放入临时变量并将表达式分解为部分。

至于实际的斐波那契，尚不清楚您为什么要传递 2 个参数。

Answer 4

虽然用递归计算斐波那契数当然是可能的，但它的性能很差。使用递归的一个非常糟糕的例子：对于每个（子）斐波那契数，必须再计算两个斐波那契数。

一种更快、更简单的方法使用迭代，可以在这里找到：

https://stackoverflow.com/a/56136909/1516636

Answer 5

短版，递归

fib(){(($1<2))&&echo $1||echo $(($(fib $(($1-1)))+$(fib $(($1-2)))));}