bashの関数は再帰呼び出しが可能か
bashで本格的な数値演算プログラムとかを組む人は少ないだろう。本格的にプログラムするのであればCとかJavaとか使うだろうし、スクリプトで組むとしてもPerlとかが一般的ではないだろうか。だからbashで関数を使う人なんてそれほど多くはないと思う。 なので「bashの関数は再帰呼び出しが可能か」なんてことを気にする人はいないだろう。
仮想ディスクの総セクタ数からジオメトリ(セクタ数、ヘッド数、シリンダ数)の構成を作ったり(⇒)、ディスクのバックアップを取る時に総バイト数を因数分解したブロック数を算出したいということが結構あって、与えられた数字を素因数分解するプログラムを作ろうと思った。(効率を求めようなどと変な気を起こさなければ)大したプログラムでもないので、わざわざCで作る程のことでもない。また、わざわざPerlをインストールするのも頂けない。まぁ、シェルスクリプトで作るのが妥当だろう。
一方、ある数を素因数分解するアルゴリズムは色々あると思うが、(効率を求めようと変な気を起こさなければ)関数の再帰呼び出しで作るのが一番自然だと思う。Nを素因数分解する場合、N = P * N’ となる最小の素数Pを1つ求めれば、あとは再帰的にN’を素因数分解すれば答えは求めれられる。
で、ふと思ったのは、bashの関数は再帰呼び出しが出来るのか?という疑問である。最初、私は「無理だろう!」と感じていた。bashはプログラミング言語というよりはコマンドインタプリタであるし、関数といってもどちらと言えばマクロ定義の性格が強い。が、まぁ、やってみることにした。
#! /bin/bash function factor () { num=2 while [ ${num} -le `expr ${1} / ${num}` ]; do if [ `expr ${1} % ${num}` -eq 0 ] ; then echo -n " * ${num}" factor `expr ${1} / ${num}` return else num=`expr ${num} + 1` fi done echo " * ${1}" } if [ "${1}" == "" ]; then echo "Usage: ${0} number" exit 1 fi echo -n "1" factor ${1}
で実行すると、
[root@linux tmp]# ./factor 63063 1 * 3 * 3 * 7 * 7 * 11 * 13 [root@linux tmp]#
ちゃんと答えがでる。bashの関数はちゃんと再帰呼び出しが可能ということか。
上のプログラムでは関数のローカル変数としてnumというシェル変数を使っているが、再帰呼び出しの後は参照していないので、ちゃんとスタックされているか分からない。そこで、変数の値の変化だけに注目した次のような関数を作ってみた。(ロジックそのものは上のfactorと同じ。関数の引数とnumというシェル変数の変化だけを出力している。)
#! /bin/bash function factor () { num=2 while [ ${num} -le `expr ${1} / ${num}` ]; do if [ `expr ${1} % ${num}` -eq 0 ] ; then echo " ${1},${num} ->" factor `expr ${1} / ${num}` echo " -> ${1},${num}" return else num=`expr ${num} + 1` fi done } if [ "${1}" == "" ]; then echo "Usage: ${0} number" exit 1 fi factor ${1}
これを実行すると次のようになる。
[root@linux tmp]# ./prog 63063 63063,3 -> 21021,3 -> 7007,7 -> 1001,7 -> 143,11 -> -> 143,4 -> 1001,4 -> 7007,4 -> 21021,4 -> 63063,4 [root@linux tmp]#
どうも関数内で定義してもシェル変数はグローバル変数的に扱われてしまう。関数の引数はちゃんとスタック化されローカル変数として扱われるのだが。これでは再帰的なプログラムは書けない。
しかし、ちょっとヒネルとこれもなんとかなる。普段bashを使っていてサブシェル内で代入したシェル変数は元のシェルには伝わらないことで良く頭を悩ますが、これを逆手に取ればいい。
#! /bin/bash function factor () { ggg=2 ( num=2 while [ ${num} -le `expr ${1} / ${num}` ]; do if [ `expr ${1} % ${num}` -eq 0 ] ; then echo " ${1},${num},${ggg} ->" factor `expr ${1} / ${num}` echo " -> ${1},${num},${ggg}" return else num=`expr ${num} + 1` ggg=${num} fi done ) } if [ "${1}" == "" ]; then echo "Usage: ${0} number" exit 1 fi factor ${1}
[root@linux tmp]# ./prog 63063 63063,3,3 -> 21021,3,3 -> 7007,7,7 -> 1001,7,7 -> 143,11,11 -> -> 143,11,2 -> 1001,7,2 -> 7007,7,2 -> 21021,3,2 -> 63063,3,2 [root@linux tmp]#
“ ( ) ”のサブシェル内で定義されたシェル変数numはローカル変数として扱われる。一方、サブシェルの外側で定義されているgggはグローバル変数として扱われる。
それでは、関数の戻り値ある場合は? 次のような階乗を計算するプログラムで実験してみた。
#! /bin/bash function factorial () { if [ ${1} -eq 1 ]; then return 1 else factorial `expr ${1} - 1` return `expr $? \* ${1}` fi } if [ "${1}" == "" ]; then echo "Usage: ${0} number" exit 1 fi factorial ${1} echo $?
[root@linux tmp]# ./factorial 5 120 [root@linux tmp]#
問題なく使える。(但し、関数やコマンドの戻り値は0〜255なので5の階乗までしか計算できない。本来、戻り値はそういった使い方のためにあるのではないので仕方ない。もし、bashで階乗を計算させるのであれば、戻り値を使わないでechoを使って値を標準出力に出して、呼びだした側で“関数の出力”として拾うべきだろう。)
今回は本格的に検証したわけではないので、他にも何かあるかも知れないし、ちょっと制限があるかも知れないが、とりあえずは「bashの関数は再帰呼び出しができる」といって良いようだ。