BashでProject Euler（9） 再帰

Bash

前回の例にあるように関数はふつうに再帰できます。

gcd() {
    local n=$1
    local m=$2
    if [ $n -eq 0 ]; then
        echo $m
    elif [ $m -eq 0 ]; then
        echo $n
    else
        local d=`gcd $m $((n%m))`
        echo $d
    fi
}

d=`gcd 110 150`
echo $d     # 10

Pythonのジェネレータっぽいのもできます。実際には全然遅延評価していませんが。

#!/bin/bash

combinations() {
    a=()
    while [ $# -gt 1 ]; do
        a+=($1)
        shift
    done
    n=$1
    if [ $n -eq 1 ]; then
        for e in ${a[@]}; do
            echo $e
        done
    else
        m=${#a[@]}
        for((i=0; i<=$m-$n; ++i)); do
            for s in `combinations ${a[@]:i+1:m} $((n-1))`; do
                echo ${a[i]},$s
            done
        done
    fi
}

combinations 2 3 4 5 6 7 3

最後に、分割統治法の例として、マージソートを書いてみましょう。

#!/bin/bash

merge_sort() {
    local a=($@)
    L=${#a[@]}
    if [ $L -eq 1 ]; then
        echo $1
    else
        mid=$((L/2))
        b=(`merge_sort ${a[@]:0:mid}`)
        c=(`merge_sort ${a[@]:mid}`)
        L1=${#b[@]}
        L2=${#c[@]}
        k=0
        l=0
        while((k < L1 && l < L2)); do
            n1=${b[k]}
            n2=${c[l]}
            if((n1 <= n2)); then
                echo $n1
                ((k += 1))
            fi
            if((n1 >= n2)); then
                echo $n2
                ((l += 1))
            fi
        done
        
        for(( ; k < L1; ++k)); do
            echo ${b[k]}
        done
        for(( ; l < L2; ++l)); do
            echo ${c[l]}
        done
    fi
}

merge_sort 4 1 7 2 5 6 3