再帰とローカル変数
調査環境
HSP3での再帰の実装について真面目に調べてみました。 余り使う機会のないものだと思いますが、どなたかの参考になれば幸いです。 なお、調査環境は、HSP3.5、Windows10です。
参考資料：再帰的なアルゴリズムの実例集
再帰とは
再帰とは、命令や関数の記述の中で自分自身の命令や関数が呼び出されていることを指します。またこのような関数を再帰関数と呼びます。 HSP3の書式で書いてみるとこのようになります。
#deffunc meirei int a
meirei 123
return
「この命令って終わらなくね？」と思った方、正解です。この例の場合、一度実行したらエラーで止まるまで終わりません。 では次に正しく動作する再帰関数はどのように書くのか見ていきます。
正しく動作する再帰関数
正しく動作する再帰の例を見ながら説明していきます。
#module
; 数値を1ずつ減らしながら、経過を表示
#deffunc cntdown int n
mes "再帰：" + n
; 脱出条件
if n<=0 : return
; 再帰
cntdown n-1
return
#global
; 使用例
cntdown 5正しく動作する再帰関数を作るには必ず守らなければならない点がHSP3の場合は３つあります。
- 脱出条件を用意する。
- 必ず脱出条件に収束するようにする。
- 再帰を繰り返す回数が多くなりすぎないようにする。
脱出条件は再帰のループを終了するための条件です。これがないと無限ループになってしまい関数が終わりません。この例ではn<=0が脱出条件です。
またループをいくら繰り返しても脱出条件に到達しないような作りになっているような場合、これも無限ループになってしまいます。この例では再起するたびにnが1ずつ小さくなっていくので、いつか必ずn<=0を満たします。
HSP3で再帰を行うと、gosub～returnやrepeat～loopで入れ子構造を作ったときのように入れ子（ネスト）をカウントしています。ネスト回数が上限値を超えるとエラー（スタック領域のオーバーフロー）を起こして終了してしまいます。
例えば最初に「再帰とは」で書いたサンプルを私の環境で動かすと510回のループでエラーが起きました。他の言語と比較すると上限回数がとても小さいので注意が必要な部分です。
言語によらず再帰はスタックオーバーフローの問題を抱えているので、取扱には注意が必要です。
再帰を使う前に、出来る限りrepeat～loopに置き換えられないか検討したほうがいいようです。
参考資料（多言語での再帰呼出し上限回数）
再帰呼び出しに関しての暇つぶし実験
ローカル変数
プログラミング・マニュアルやHSP3 モジュール機能ガイドに少しだけ再帰の事が書かれており、ローカル変数を使用することが推奨されています。
しかし実際には前述した例にあるような簡単な計算ではローカル変数は必要ありません。 と言ってもやはり少し凝った再帰関数を作る場合はローカル変数が必要になります。
そこでモジュール内の関数定義部でのローカル変数の使い方をよく知っておく必要があります。
#module
;///////////////////////////////////////////////////////////////////////////////////////////////////
;
; ローカル変数の例
;
;[ Infomation ]
; lhensu prm
; prm=0～(0) : 整数
;
; return : 0
;
;[ comment ]
; localに続いて指定された名前はローカル変数となります。
; 見た目では引数のように見えますが引数ではありません。
; ローカル変数は、新規命令が実行されたタイミングで初期化されます。
;
; 通常HSPでは、変数はグローバルなものとして常に値を保持しますが、
; ローカル変数の場合はこの命令が実行された時に作成され、returnする際に破棄されます。
;
#deffunc lhensu int prm, local a
; ローカル変数
mes "ローカル変数 = " + a
a = prm
mes "引数代入後 = " + a
; グローバル変数
; b = 0 ; このように最初に初期化すれば一見ローカル変数と同じ動作に見えるが…
mes "グローバル変数 = " + b ; ←前回命令実行した時の値が残る
b = prm
mes "引数代入後 = " + b
return
#global
;-------------------------------------------------------------------------------
lhensu 123
mes "-----"
lhensu 456
実行結果
ローカル変数 = 0
引数代入後 = 123
グローバル変数 = 0
引数代入後 = 123
-----
ローカル変数 = 0
引数代入後 = 456
グローバル変数 = 123
引数代入後 = 456
localに続いて指定された名前はローカル変数となります。 見た目では引数のように見えますが引数ではありません。 ローカル変数は、新規命令が実行されたタイミングで初期化されます。
通常HSPでは、変数はグローバルなものとして常に値を保持しますが、 ローカル変数の場合は、登録した命令が実行された時に作成され、returnする際に破棄されます。
今回の例では関数呼び出し時に使用する変数を0で初期化してしまえばローカル変数と同じ動作になりますが、 マニュアルにはローカル変数の使用は重くなると書いてあるので、グローバル変数で対応できるならグローバル変数で対応したほうがいいようです。
階乗
ローカル変数を使った再帰の前に、代表的な再帰関数の例として階乗の計算を見てみます。 階乗の計算は、再帰関数の例としてよく取り上げられます。
#module
;/////////////////////////////
;
; 階乗
;
;[ Infomation ]
; res = fact( n )
; n=0～(0) : 正の整数
;
; return : n! = n * (n-1) * (n-2) * … * 1
;
;[ comment ]
; nの階乗（n!）を計算します。
; nは正の整数を指定してください。
;
#defcfunc fact int n
if n = 0 {
; 脱出条件
; 0! = 1
return 1
}
; 再帰呼び出し
; n! = (n-1)! * n
return fact(n-1) * n
#global
; 使用例
mes "5! = " + fact(5)
階乗とは…詳細は各自調べてもらうとして、5の階乗の場合はこんな計算です。
5! = 5 * 4 * 3 * 2 * 1 = 120
脱出条件は n=0 です。
入力値nは再帰を繰り返すたびに-1されて行き、いずれはn=0に到達して脱出条件を満たします。
なお、この例では最初の引数に負数を入力するとn=0に収束しないので、無限ループになってしまいエラーで終了してしまいます。
階乗の解説とローカル変数の使用例
ローカル変数とグローバル変数を使いわけながら、階乗の計算を詳しく見ていきます。
#module
;///////////////////////////////////////////////////////////////////////////////////////////////////
;
; 階乗
;
;[ Infomation ]
; res = fact( n )
; n=0～(0) : 正の整数
;
; return : n! = n * (n-1) * (n-2) * … * 1
;
;[ comment ]
; nの階乗（n!）を計算します。
; nは正の整数を指定してください。
;
;計算途中を表示しながら計算していきます。
;ローカル変数を使うサンプルです。
;
#defcfunc fact int n, local l_n
; 関数が呼ばれたら表示
mes strf("%02d : call fact( %d )", i, n)
; 実行順番
; ここの i は、staticな変数なので再帰しても0にリセットされません。
i++
; 入力値をローカル変数に保存
l_n = n
; 脱出条件
if n = 0 {
; 0! = 1
mes strf("%02d : fact(%d) = 1", i, n)
i++
return 1
}
; 再帰
; n! = (n-1)! * n
res = fact(n-1) * n
; 再帰で計算が終わる順に計算手順を表示
; 再帰先で l_n に別の値が代入されても、呼び出し元の l_n は影響を受けず元の値のままとなる。
; i : fact(n) = fact(n-1) * n
s = strf("%02d : fact( %d )", i, n)
s+= strf(" = fact( %d-1 ) * %d", l_n , l_n)
s+= strf(" = fact( %d ) * %d", l_n-1, l_n)
s+= strf(" = %d", res)
mes s
; 実行順番
; ここの i は、staticな変数なので再帰しても0にリセットされません。
i++
; 戻る
return res
#global
;-------------------------------------------------------------------------------
mes "5! = " + fact(5)
実行するとこのような結果が出力されます。
実行結果
00 : call fact( 5 )
01 : call fact( 4 )
02 : call fact( 3 )
03 : call fact( 2 )
04 : call fact( 1 )
05 : call fact( 0 )
06 : fact(0) = 1
07 : fact( 1 ) = fact( 1-1 ) * 1 = fact( 0 ) * 1 = 1
08 : fact( 2 ) = fact( 2-1 ) * 2 = fact( 1 ) * 2 = 2
09 : fact( 3 ) = fact( 3-1 ) * 3 = fact( 2 ) * 3 = 6
10 : fact( 4 ) = fact( 4-1 ) * 4 = fact( 3 ) * 4 = 24
11 : fact( 5 ) = fact( 5-1 ) * 5 = fact( 4 ) * 5 = 120
5! = 120
まずは再帰が処理される順番から見ていきます。
(00～05) 脱出条件に到達するまで計算の保留を積み重ねます。
(06) 脱出条件に到達したら計算を逆にたどっていきます。
(07～10) 保留にしていた計算を一番新しい保留から順に計算していきます。
(11) 最初のfact関数実行時に戻ったときには必要な数値はすべて揃っているので、最終的な答えが算出されます。
算数の計算みたいですね。先にカッコの中を計算するんですが、その中にカッコがあればそっちを先に計算する…みたいな。
次は再帰関数内のグローバル変数とローカル変数について見てみます。
この例の場合、それぞれ次のようになっています。
グローバル変数 i
ローカル変数 l_n
グローバル変数は使い慣れていると思いますが一応説明してみます。
モジュール空間内で使用している通常の変数は、静的（static）な変数です。新たに代入や初期化（dim等）しない限りモジュール空間内で生き続け、モジュール空間内ならどこで呼び出しても入っている値を取り出せます。
物理的には変数1個分のメモリ領域を確保して、代入等はその領域を上書きして利用しているのでしょう。（多分）
グローバル変数を使うと、自作命令に引数をたくさんつけなくてもよくなるのでなかなか便利な代物です。再帰で呼び出しても同じモジュール空間内なので元の値を持ったまま使用することができます。
例ではカウンタとして利用しています。
一方ローカル変数は、公式でも使用例があまりないのであまり馴染みがないと思います。
#deffunc、#defcfunc のパラメータでlocalを指定した変数はローカル変数となります。
ローカル変数はグローバル変数と違い、使用できる有効範囲（変数のスコープ）という物が存在します。ローカル変数はこの範囲の外では使用することができません。ここで取り扱っているローカル変数の有効範囲は、実行した関数からreturnで抜けるまでの間です。
returnで抜けるまでの間に命令・関数やgosubなどでジャンプした場合、ジャンプ先では元の場所のローカル変数へはアクセスできません。
ジャンプ先から元の関数内に戻ってくれば、再びローカル変数にアクセスできるようになります。
ローカル変数へアクセスできるのは、ローカル変数をパラメータで宣言した命令・関数の中だけです。（基本的には）
物理的にはローカル関数を持った命令・関数が呼び出されるたびに毎回変数1個分のメモリが確保され、returnで命令・関数を抜けるたびにメモリから開放されているのだろうと思われます。
再帰で何重にも呼ばれ、ネストが深くなるほどローカル関数のためのメモリ領域は沢山消費されていくことになります。（多分）
再帰でローカル変数を使用すると、ジャンプ元やジャンプ先からの影響を受けない変数を持っておくことができます。 これは、再帰先でも同じ変数名を使用しなければいけない再帰の仕組みにとっては便利な機能です。 しかしローカル変数は、呼ばれるたびに初期化作業が行われるため、普通にグローバル変数を使うよりも比較的負荷が増えます。（と、マニュアルに書いてあります。） 便利だからと無闇矢鱈と使うのではなく、どうしても必要な場合だけ使うようにしましょう。
ローカル変数の使い所
グローバル変数にすべきかローカル変数にすべきか、迷うことがあると思います。 私が思いついた範囲での判断基準を書いてみましたので、何かの時に参考になれば幸いです。
グローバル変数を使うべき場面
実行のたびに初期化されると困る場合はグローバル変数
#defcfunc hogehoge
mes "" + count + "回目"
count++
return
関数の外でもその変数にアクセスしたい場合はグローバル変数
#defcfunc hogehoge int a
b = a
gosub *fugafuga
mes b
…
return
*fugafuga
b++
return
ローカル変数を使うべき場面
関数の外から戻ってきた後もその変数を使う場合はローカル変数
#defcfunc hogehoge int a, local b
b = a
res = hogehoge(a-1)
mes b
…
総和
ここからはHSP3での再帰関数の実装例を見ていきます。
まずは簡単な「総和」から。
1 + 2 + 3 + 4 + …
の計算結果を算出する例です。数学ではシグマを使って表現されるあれですね。
答えだけなら簡単な計算式で出てきますが、ここでは再帰を使って実装してみます。
#module
;///////////////////////////////////////////////////////////////////////////////
;
; 1～nまでの総和
;
;[ Infomation ]
; res = sigma( n )
; n=0～(0) : 非負整数
;
; return : 数列の話
;
;[ comment ]
; 1～nまでの整数を足し合わせた数を算出します。
; 簡単な計算式で算出できますが、あえて再帰で表現してみます。
;
#defcfunc sigma int a
if a = 0 {
return 0
}
return sigma(a-1) + a
#global
;-------------------------------------------------------------------------------
; 再帰
mes "総和 1+2+…+9+10 = " + sigma(10)
; ループ
i = 0
repeat 10, 1
i+=cnt
loop
mes "総和 1+2+…+9+10 = " + i
; 計算式
n = 10
mes "総和 1+2+…+9+10 = " + ( n*(1+n)/2 )
計算式で答えが出るものは、計算式で処理したほうが計算負荷が小さいので早く処理できます。 なるべく計算式を使いたいですね。
最大公約数
最大公約数とは、2つ以上の整数の公約数（整数で割り切れる数）のうちの最大の正整数のことです。 この例では2つの整数の最大公約数を算出します。 「ユークリッドの互除法」というアルゴリズムを使用して算出します。
#module
;///////////////////////////////////////////////////////////////////////////////
;
; 最大公約数（GCD）
;
;[ Infomation ]
; res = gcd( a, b )
; a, b : 非負整数
;
; return : aとbの最大公約数
;
;[ comment ]
; ユークリッドの互除法を用いて最大公約数を計算します。
; a, b が0以上の整数であるとする
;
#defcfunc gcd int a, int b
if b = 0 {
; 脱出条件
; a/bがゼロ除算になるので |a| を返す。
return abs(a)
} else {
; 再帰呼び出し
; gcd( b, mod(a, b) )
; 常に b > a\b なので必ず b=0 に収束していく。
return gcd(b, a\b)
}
#global
;-------------------------------------------------------------------------------
mes "最大公約数( 640, 480) => " + gcd( 640, 480)
mes "最大公約数(1280, 800) => " + gcd(1280, 800)
mes "最大公約数(1920, 1080) => " + gcd(1920, 1080)
mes "最大公約数(1920, 1200) => " + gcd(1920, 1200)
mes "最大公約数(2560, 1440) => " + gcd(2560, 1440)
mes "最大公約数(3840, 2160) => " + gcd(3840, 2160)
mes "最大公約数(7680, 4320) => " + gcd(7680, 4320)
ハノイの塔
バラモンの塔やルーカスタワーとも呼ばれるそうです。かっこいい名前ですね。 ルールに従って円盤を移動するおもちゃなのですが…詳しくは調べてください。 手順の解法に再起的アルゴリズムが有効で、再帰関数の例としてもよく採り上げられます。
#module
;///////////////////////////////////////////////////////////////////////////////
;
; ハノイの塔
;
;[ Infomation ]
; hanoi disk, from, to
; disk=0～(0) : 板枚数（非負整数）
; from : 移動元（A～C）
; to : 移動先（A～C）
;
;[ comment ]
; ハノイの塔の手順を表示する命令です。
;
; nは円盤の総数です。
; ３本の棒にはA,B,Cの名前が与えられています。
; from、toには棒の名前として、A～Cの重複しない文字列を指定してください。
;
#deffunc hanoi int disk, str _from, str _to
; 等に名前を設定
RODS = "A", "B", "C"
; 手順を表示
_hanoi disk, _from, _to
return
;///////////////////////////////////////////////////////////////////////////////
;
; ハノイの塔手順を表示（モジュール内でのみ使用できる命令）
;
;[ Infomation ]
; hanoi( n, from, to )
; n=0～(0) : 板枚数（非負整数）
; from : 移動元（A～C）
; to : 移動先（A～C）
;
;[ comment ]
; ハノイの塔の手順を表示する命令です。
;
; nは円盤の総数です。
; ３本の棒にはA,B,Cの名前が与えられています。
; from、toには棒の名前として、A～Cの重複しない文字列を指定してください。
#deffunc local _hanoi int n, str from, str to, local temp
; 脱出条件
if n=0 : return
; 仲介場所を決定
; 移動元でも移動先でもない場所
if (from!"A") & (to!"A") : temp="A"
if (from!"B") & (to!"B") : temp="B"
if (from!"C") & (to!"C") : temp="C"
; 移動
_hanoi n-1, from, temp
mes "円盤 " + n + " を " + from + " から " + to + " に移動"
_hanoi n-1, temp, to
return
#global
;-------------------------------------------------------------------------------
hanoi 4, "A", "C"
フィボナッチ数列
みんな大好きフィボナッチ数列です。
- ヒマワリの螺旋の数。
- フィボナッチ数列の隣り合う 2 項の比は黄金比に収束する。
などの性質が有名でしょうか。
実際の数値列はこのようなものです。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
最初の0,1は決まっていて、直前の2つの数の和が次の数字となります。
0+1=1
1+1=2
1+2=3
2+3=5
…
というように算出します。
#module
;///////////////////////////////////////////////////////////////////////////////
;
; フィボナッチ数列
;
;[ Infomation ]
; res = fibonacci( n )
; n=0～(0) : 非負整数
;
; return : フィボナッチ数列
;
;[ comment ]
; n番目（0～）のフィボナッチ数列を算出します
;
; 配列変数に結果を保存するのでその分メモリを消費します。
;
#defcfunc _fibonacci int m
if m > 1 {
table(m) = _fibonacci(m-2) + _fibonacci(m-1)
}
; 脱出条件
; m<=1
return table(m)
#defcfunc fibonacci int n
dim table, n
table = 0,1
return _fibonacci(n)
;///////////////////////////////////////////////////////////////////////////////
;
; フィボナッチ数列（実装例２）
;
;[ Infomation ]
; res = fibonacci2( n )
; n=0～(0) : 非負整数
;
; return : フィボナッチ数列
;
;[ comment ]
; n番目（0～）のフィボナッチ数列を算出します
;
; fibonacci関数よりも1.6倍ほど遅いようです。
;
#defcfunc fibonacci2 int n
switch n
case 0
; 脱出条件
f = 0
swbreak
case 1
; 脱出条件
f = 1
swbreak
default
; n = 2～
f = fibonacci2(n-2) + fibonacci2(n-1)
swbreak
swend
return f
#global
;-------------------------------------------------------------------------------
m = ""
repeat 11
m += "" + fibonacci(cnt) + ", "
loop
mes "フィボナッチ数列：" + m + "…"
mes "30 => "+fibonacci(30)
mes "30 => "+fibonacci2(30)
; ループ
c = 30
n0 = 0
n1 = 1
repeat c-1
n2 = n0 + n1
n0 = n1
n1 = n2
loop
mes "30 => "+n1
switch～caseを使うよりも配列変数に計算結果を貯めていくほうが計算が早いようですね。 また、フィボナッチ数列はビネの公式という数式でも求めることができます。
偶奇判定
再帰は自分の中で自分自身を呼び出す以外に、一旦他の関数を経由してから自分を呼び出す場合もあります。 その例として奇数と偶数を判定する例です。
#module
;///////////////////////////////////////////////////////////////////////////////
;
; 偶奇判定
;
;[ Infomation ]
; res = even( n )
; n=0～(0) : 非負整数
;
; return : 1=偶数、0=奇数
;
;[ comment ]
; nが奇数か偶数かを判定します。
;
; 偶数
#defcfunc even int n
if n=0 {
; 0は偶数
; 脱出条件
return 1
} else {
return odd(n-1)
}
#defcfunc odd int n
if n=0 {
; 脱出条件
return 0
} else {
return even(n-1)
}
#global
;-------------------------------------------------------------------------------
; 再帰で判定
mes even(4)
mes even(7)
; 計算式で判定
mes 4\2=0
mes 7\2=0
1個の関数で終わってくれれば簡単なのに…あまり遭遇したくない関数です。(´・ω・｀)
最後に
以前からHSP3でも再帰が出来るという事は知っていたのですが、再帰ってよくわからないし、何に使うのか分からず、必要もないので放置したままになっていました。 最近ちょっと必要になったので調べてみたのですが、マニュアル含めてもあまり情報がない部分で大変困りました。 上限回数も極端に小さいところを見ると、HSP3ではあまり推奨していない機能なのかもしれませんね。