プチコンで遊ぼう! (はてなブログ版)

任天堂3DSのプチコンで遊ぼう! [twitter:@eida_s]

はてなダイアリーから移行しました。 はてなダイアリーのURLを開いても自動的にこちらにリダイレクトされますのでご了承ください。

プチコンでムリヤリ再帰処理

昨日(2月1日)ツイッターでつぶやいた、プチコンでムリヤリ再帰処理について。
後でその時つぶやいた140フィボナッチを例に解説します。

プチコンはローカル変数がないので再帰処理できない、と言うのが一般的な話ですが、ローカル変数がどのように実現されているかを考えると、実はそれを自前でやれば再帰処理(らしきもの)は可能です。

Javascriptで書いた簡単な再帰処理の例です。階乗を求めています。

function factorial(x) {
  if (x==1) 
    return 1;
  else
    return x*factorial(x-1);
}
document.write(factorial(10));

factorialの最後で return x*factorial(x-1); とありますが、このxとfactorial(x-1)の呼び出し先でのxは別もののはずです。
仮に別ものでないとすると、このxは、factorial(x-1)の中で上書きされてしまい、xとfactorial(x-1)を掛け算(*)しようとした時におかしな値になってしまいます。

このようにfactorialは一度呼び出される毎に、その中で使うメモリは新たに確保されます。
10段の再帰がなされている時、一番深いところでは、factorial 10個分のメモリが確保されていることになります。


ではこれと同じようなことをプチコンでやるにはどうしたら、よいでしょうか。
もっとも簡単な方法は、スタックを使ってサブルーチン内で使う変数を保存することです。
といってもスタックの構造をプチコンが持っているわけではないので、配列で擬似的にスタック構造を実現します。

スタックを使って再帰らしきものを実現してみたのが140フィボナッチです。
フィボナッチ数を再帰処理を使って求めるものです。
(本当はハノイの塔をやりたかったのですが、140文字では無理でした。)

140フィボナッチそのままではスタックを使った再帰がわかりずらいので、それをわかりやすく書き直したのが次のコードです。

CLEAR:DIM S(99)      'S()はスタック
P=0                               'Pはスタックポインタ
N=15
GOSUB @2              'N=15の時のサブルーチン呼び出し
END

@2
'N, F, F1, F2 はローカル変数
'S(), P はグローバル変数

IF N<2 THEN F=1:RETURN

S(P)=N:P=P+1         '再帰呼び出し前に、ローカル変数Nの値をスタックに保存
                     'P=P+1でスタックポインタを進める
                     '※スタック保存するのはここまでに使った変数だけでよい
N=N-1:GOSUB @2:F1=F  '再帰呼び出し
P=P-1:N=S(P)         'スタックからローカル変数Nを取り出し
S(P)=N:P=P+1         'ローカル変数Nの値をスタックに保存
S(P)=F1:P=P+1        'ローカル変数F1の値をスタックに保存

N=N-2:GOSUB @2:F2=F  '再帰呼び出し
P=P-1:F1=S(P)        'スタックからローカル変数F1に値を取り出し
P=P-1:N=S(P)         'スタックからローカル変数Nに値を取り出し

F=F1+F2
?F
RETURN

140フィボナッチは上記のコードを140文字でどうにかおさめるように書き直したものです。

CLEAR:DIM S(99)N=15GOSUB@2:END↓
@2↓
IF N<2THEN F=1RETURN↓
S(P)=N:P=P+1N=N-1GOSUB@2:N=S(P-1)-2S(P)=F:P=P+1GOSUB@2:F=F+S(P-1)P=P-2N=S(P)?F:RETURN