遞歸調用bash（加泰羅尼亞語數字）

Question

我試圖創建一個程序，該程序列出所有catalan數字低於或等於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，腳本將運行。

我設法讓程序以類似的代碼到你的工作：

#!/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" 

有在第二個問題CALL1和CALL2的值需要乘，不添加。改變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將執行第十（10）僅有4毫秒Catalan數。

許多回聲被包括在內以「看」節目的工作方式。您可以取消引用他們。

儘管有一個限制，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毫秒。