在 bash 中仅使用 1 个变量使用递归打印斐波那契数列

Question

我想知道如何在 bash 中仅使用 1 个变量使用递归打印斐波那契数列。

根据我所做的：

fib()
    {
    i=
    if (( $i <= 1 ))
    then echo 0
    elif (( $i == 2 ))
    then echo 1
    else

    echo $(( $(fib $(($i - 1)) ) + $(fib $(($i - 2)) ) ))

fi
 }

echo $(fib )

我得到了最终迭代的正确输出，例如，如果我输入 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循环，但我不想使用另一个变量。

Answer 1

bash 中的变量默认是全局的。您需要将 i 显式设为本地。

 fib () {
     local i
     i=
     if (( i <= 1 )); then
         echo $i
     else
         echo $(( $(fib $((i-1)) ) + $(fib $((i - 2)) ) ))
     fi
}

（此外，如果您从 0 开始，您的基本情况会有点偏离，并且 2 不必是基本情况；fib 2 可以从基本情况 fib 0 和 fib 1.)

Answer 2

如果你想打印从 1 到 $n 的每个斐波那契值，我建议：

fib_r() {
    local i=
    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 <= ; i++ )); do
        fib_r $i
    done
}

fib 10

产出

它仍然是一个变量，尽管每个函数一个。

我在递归函数中使用了 bash 变量 $FUNCNAME ，因此您不必在函数名称中硬编码函数名称。当我重命名该函数时，我没有更新那行，这让我有点生气。

当然，如果缓存结果，您的性能会大大提高："fib 16" 在我的 VM 上，不缓存大约需要 3.5 秒，缓存大约需要 0.03 秒.

fib_r() {
    local i=
    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<=; i++)); do
        fib_cache[i]=$(fib_r $i)
        echo "${fib_cache[i]}"
    done
}

Answer 3

只是为了（我的）乐趣，此代码使用不使用变量的递归函数打印从第 0 位到第 92 位的斐波那契数（如 Fibonacci number - Wikipedia 中所定义）：

#! /bin/bash

function fib
{
    echo ${3-0}

    (( > 0)) && fib $((-1)) ${3-0} $((${2-1}+${3-0}))
}

fib 92

有些人可能会声称使用位置参数（</code>、<code>、</code>）是作弊，但其他解决方案可以说是使用两个变量（ <code>$i 和 ).

代码在我的（旧的）Linux 机器上运行不到 0.01 秒。

该代码应该可以在任何平台上使用 Bash 版本 3 或更高版本处理最多 92 个数字。参见 Bash Number Limit?。大于 93 的数字将导致代码因算术溢出而产生垃圾结果。

在 bash 中仅使用 1 个变量使用递归打印斐波那契数列

Print Fibonacci series using recursion in bash with only 1 variable

bash

recursion

fibonacci