bash（catalan-numbers）の再帰呼び出し

Question

bashスクリプトの引数以下のすべてのカタロン番号をリストするプログラムを作成しようとしています。これは私が現在持っているが、それは私にstackoverflowエラーを与える（私はエラーがforループにある必要がありますが、私は理由を把握することはできませんと信じて）。私はこのプログラムをJavaで作っています。それが動作するので、構文エラーでなければならないと思いますか？

#!/usr/bin/env bash 
pcat=0 

Cat() { 

res=0 

    if [ $1 -le 1 ] 
    then 
     echo 1 
     return 1 
    fi 

    for ((i=0; i<$1; i++)) 
    do 
     var1=$(($1-($i+1))) 
     call1=$(Cat $i) 
     call2=$(Cat $var1) 

     res=$((res+call1+call2)) 
    done 

echo ${res} 
return res 

} 


while [ $pcat -lt $1 ] 
do 
    Cat $pcat 

    pcat=$((pcat+1)) 
done 

Answer 1

あなたがreturn resを行うラインはリターンが一般的には128未満の数字と数字のみで対処することができ、間違っています。

あなたが意味するものがreturn $resだったとすると、スクリプトが実行されます。

Call1とCall2の値を乗算する必要があるという点で、第二の問題がありました

#!/bin/bash 
catalan() { 
    local n=$1 
    #echo "called with $n" >&2 

    if ((n <= 1)); then 
     res=1 
    else 
     res=0 
     for ((i=0; i<n; i++)) 
     do 
      var1=$((n-i-1)) 
      call1=$(catalan $i) 
      call2=$(catalan $var1) 
      res=$((res+call1*call2)); 
      #echo ":$i:$var1: result Call1:$call1: and Call2:$call2: $res" >&2 
     done 
    fi 
    #echo "result is ${res}" >&2 
    echo "$res" 
} 

n=$1 
until ((pcat > n)) 
do  catalan "$((pcat++))" 
done 


echo "all was done" 

、追加されません：

は、私はあなたのようなコードでの作業プログラムを得ることができました。 res+call1+call2を次のように変更しました：

res=$((res+call1*call2)) 

ただし、結果のコードは非常に遅いです。十分の一（10）のカタロニア数を計算するのに、コードは16秒かかりました。

---

単一の配列の中に値を保持する完全に新しいプログラム：catarray。このよう

：

#!/bin/bash 

# some initial values to jump start the code: 
catarray=(1 1 2 5) 

############################################################################# 
catalan(){ 
    #echo "making call for $1" >&2 
    local n=$1 
    # ${#catarray[@]} is the count of values in catarray (last index + 1). 
    # if the number n to be found is not yet in the array of values of 
    # catarray then we need to calculate it. Else, we just print the value. 
    if ((n >= ${#catarray[@]})); then 
     #echo "$n is bigger than ${#catarray[@]}" >&2 
     # this is a new number, lets loop up till we 
     # fill the array just up to this value 
     for ((i=${#catarray[@]};i<=n;i++)); do 
     #echo "fill index $i in array" >&2 
     # calculate the sum of all terms for catalan of $n. 
      for((j=0;j<i;j++)); do 
       ((catarray[i] += catarray[j] * catarray[i-j-1])) 
       #echo "done math in $i for $j with ${catarray[j]} * 
       #echo "* ${catarray[i-j-1]} = ${catarray[i]}" 
      done 
     done 
    fi 
    # After making the math or else we just print the known value. 
    #printf 'result of catalan number is %s\n' "${catarray[n]}" 
} 
############################################################################# 
catalan "$1" 

printf '%s, ' "${catarray[@]}"; echo 

WICHはわずか4ミリ秒第10（10）カタロニア語番号を実行します。

プログラムがどのように動作するかを見るために多くのエコーが含まれていました。あなたはそれらを引用符で囲むことはできません。

しかし、制限はありますが、bashの数字は64ビット（64ビットコンピュータの場合）または（2^63-1）の数値でなければなりません。それは最大のカタロニア数を35番目に可能にします。

$ catalan 35 
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 
2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 
6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 
4861946401452, 18367353072152, 69533550916004, 263747951750360, 
1002242216651368, 3814986502092304, 14544636039226909, 
55534064877048198, 212336130412243110, 812944042149730764, 
3116285494907301262 

しかし、これを行うには20ミリ秒かかります。