Bash 4.3+ - 递归斐波那契

Question

我正在研究编译成 bash 4.3+ 代码的编程语言。我正处于语言的最后阶段，但递归函数存在一个小问题。这是 bash 代码，它应该 return 给定索引的斐波那契数。

#!/bin/bash

function fib() {
    local a=
    declare -n ret=
    if (( $a <= 2 )); then
        ret=1
        return
    fi
    fib $((a-1)) fib1
    fib $((a-2)) fib2

    ret=$((fib1+fib2))
    echo "fib($((a-1))) + fib($((a-2))) = $ret"
    return
}

num=5
fib $num result
echo 
echo "fib($num) = $result"

此代码中的问题是 fib(5) 给出的 3 显然是错误的。我认为问题是，当我将 fib1 和 fib2 作为存储 return 值的方式传递时，它们会被分配它们的每次调用覆盖。如果那是问题所在，我怎样才能使 fib1 和 fib2 成为其执行范围的本地。

请注意，我不想对 return 值使用 return 语句，我想尝试使用 declare -n namerefs 找到解决方案。

谢谢

Answer 1

What I think the problem is, when I pass fib1 and fib2 as a way to store the return value, they get overwritten by each call which assigns them.

是的，通过在递归调用之间和递归调用之后打印 fib1 的值，您可以看到这一点：

fib $((a-1)) fib1
echo "fib($a): fib1: $fib1"
fib $((a-2)) fib2
echo "fib($a): fib1: $fib1 fib2: $fib2"

您应该会在第二次调用期间看到 fib1 的值发生变化。这是意料之中的，因为它没有声明 local 并且只有一个 fib1 的全局副本。

如果你把它们制作成本地的...这没什么用。

假设您首先调用 fib 4 result。第一次迭代将使 fib1 本地化，并调用 fib 3 fib1。现在第二次迭代也会使 fib1 局部化，但它也会尝试将其 return 值分配给同名变量。由于访问是按名称进行的，因此它将 return 值保存到 自己的 副本 fib1.

这也可以通过更简单的脚本看到，它试图从递归的底部向上 return 一个固定值：

#!/bin/bash  
foo() {         
    declare -n ret=
    if ((  == 0 )); then
        echo "foo() returning"
        ret=end          # this is the value that should bubble up
        return
    fi
    local x=initial    # use  here to track the level the value came from
    foo $(( - 1)) x
    ret=$x
    echo "foo() = $x"
    return
}
foo 3 result
echo "main:    $result"

我能想到的解决方法是为 return 值设置一个单独的全局变量，并立即将其复制到局部变量：

local fib1 fib2
fib $((a-1)) retval
fib1=$retval
fib $((a-2)) retval
fib2=$retval

Bash 4.3+ - 递归斐波那契

Bash 4.3+ - Recursive fibonacci

bash

recursion

fibonacci

bash4