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