我想知道如何使用仅有1个变量的bash中的递归来打印Fibonacci系列。
从我所做的:
fib()
{
i=$1
if (( $i <= 1 ))
then echo 0
elif (( $i == 2 ))
then echo 1
else
echo $(( $(fib $(($i - 1)) ) + $(fib $(($i - 2)) ) ))
fi
}
echo $(fib $1)
我得到了最终迭代的正确输出,例如,如果我输入10,我将得到34,但我想打印整个数字序列,即所有迭代。我怎样才能做到这一点?
我尝试的另一种方式是:
#!/bin/bash
arr[0]=0
arr[1]=1
for (( i=0; i<=10; i++ ))
do
echo -n "${arr[0]} "
arr[0]=$((${arr[0]} + ${arr[1]} ))
arr[1]=$((${arr[0]} - ${arr[1]} ))
done
echo ""
但显然我在这里使用了for循环,但我不想使用另一个变量。
只是为了(我的那种)乐趣,这段代码打印了从0th到92nd的斐波纳契数字(在Fibonacci number - Wikipedia中定义),带有一个不使用变量的递归函数:
#! /bin/bash
function fib
{
echo ${3-0}
(($1 > 0)) && fib $(($1-1)) ${3-0} $((${2-1}+${3-0}))
}
fib 92
有些人可能声称使用位置参数($1
,$2
,$3
)是作弊,但其他解决方案可以说是使用两个变量($i
和$1
)。
在我的(旧的)Linux机器上运行代码需要不到0.01秒。
在任何平台上,代码应使用Bash版本3或更高版本的数字最多92。见Bash Number Limit?。高于93的数字将导致代码因算术溢出而产生垃圾结果。
bash
中的变量默认为全局变量。你需要明确地使i
本地化。
fib () {
local i
i=$1
if (( i <= 1 )); then
echo $i
else
echo $(( $(fib $((i-1)) ) + $(fib $((i - 2)) ) ))
fi
}
(另外,如果从0开始,你的基本情况有点偏,2不必是基本情况; fib 2
可以从基本情况fib 0
和fib 1
派生。)
如果你想打印从1到$ n的每个斐波纳契值,我建议:
fib_r() {
local i=$1
if (( i < 0 )); then
echo "Error: negative numbers not allowed" >&2
exit 1
elif (( i <= 1 )); then
echo $i
else
echo $(( $($FUNCNAME $((i - 1)) ) + $($FUNCNAME $((i - 2)) ) ))
fi
}
fib() {
local i
for (( i = 1; i <= $1; i++ )); do
fib_r $i
done
}
fib 10
输出
0
1
1
2
3
5
8
13
21
34
它仍然是一个变量,尽管每个函数都有一个变量。
我在递归函数中使用bash变量$ FUNCNAME,因此您不必在其自身内部对函数名进行硬编码。当我重命名该函数时,我没有更新该行。
当然,如果你缓存结果,你的性能会大大提高:在我的VM上,“fib 16”在没有缓存的情况下大约需要3.5秒,在缓存时大约需要0.03秒。
fib_r() {
local i=$1
if (( i < 0 )); then
echo "Error: negative numbers not allowed" >&2
exit 1
elif [[ -n ${fib_cache[i]} ]]; then
echo "${fib_cache[i]}"
elif (( i <= 1 )); then
echo $i
else
echo $(( $( $FUNCNAME $((i - 1)) ) + $( $FUNCNAME $((i - 2)) ) ))
fi
}
fib_cache=()
fib() {
local i
for ((i=1; i<=$1; i++)); do
fib_cache[i]=$(fib_r $i)
echo "${fib_cache[i]}"
done
}