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を使用して解決策を探してみたいです。

はあなた、私は問題は、私は戻り値を格納するための方法として、FIB1とFIB2を渡すとき、彼らはそれらを割り当て、それぞれの呼び出しによって上書きされます、と思われるもの

Answer 1

ありがとうございます。

うん、あなたは再帰呼び出しの間と後fib1の値を印刷していることがわかります。

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

あなたは2番目の呼び出し中にfib1の変化の値が表示されるはずです。それはlocalと宣言されておらず、fib1のグローバルコピーが1つしかないので、これは予想されます。

あなたがローカルにすると...それはあまり役に立たない。

fib 4 resultを呼び出すとします。最初の反復ではfib1がローカルになり、fib 3 fib1と呼び出します。今度は2回目の反復で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