Bash 4.3+ - 递归斐波纳契

Question

我正在编写我的编程语言，编译成bash 4.3+代码。我处于我的语言的最后阶段，但我有一个递归函数的小问题。这里是应该返回给定索引的fibnacci数字的bash代码。

#!/bin/bash 

function fib() { 
    local a=$1 
    declare -n ret=$2 
    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作为存储返回值的方式时，每次调用都会被覆盖。如果这是问题，我怎样才能使fib1和fib2位于其执行范围内。

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

谢谢

Answer 1

我认为这个问题是，当我通过FIB1和FIB2的方式来存储返回值，他们得到的每一个为它们分配呼叫覆盖。

是的，你可以看到，通过打印之间以及递归调用后的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，但它也会尝试将其返回值分配给一个相同名称的变量。由于访问是按名称进行的，因此它将返回值保存到其自己的副本fib1。

这可以用太有点简单的脚本可以看出，这种尝试从递归的底部返回一个固定值了：

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

我能想到的是解决办法有一个单独的全局变量作为返回值，并立即将其复制到本地变量：

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