［Piet］10の階乗 - 趣味プログラミングの部屋

今回のテーマは「10の階乗」です。プログラミングでは定番の「再帰関数」をPietで実装します。

階乗

数学ででてくる「10!」というもので、 10から1までの整数全ての積のことです。具体的に計算すると、

10!=10×9×8×...×2×1=3628800

となります。

再帰関数

プログラミングで使われる「再帰関数」とは、内部で自分自身を呼び出すような関数です。

繰り返し処理の中には、「再帰関数」を利用すると、プログラムの記述が非常に簡単になるものがあります。

先ほどの「階乗」は、

10!=10×9×8×...×2×1=10×(9×8×...×2×1)=10×9! 9!=9×8×7×...×2×1=9×(8×7×...×2×1)=9×8!

のように、

x!=x・(x-1)!

と書け、ある数の階乗計算には 元の数から1引いた数の階乗計算の結果を使えます。

こういう計算は再帰関数と相性がよいです。例えばC++では次のように実装されます。

#include <iostream>

int f(int x)
{
  if(x==0){ return 1; }
  else { return x*f(x-1); }
}

int main()
{
  std::cout << f(10) << std::endl;
  return 0;
}

関数fの中で、

引数xが0なら1を返す
引数xが0でないならx*f(x-1)を返す

というように、返り値にこの関数自身fが含まれています。

ちなみに再帰関数を使わないと、for文で次のように書くことになります。

#include <iostream>

int main()
{
  int x=1;
  for(int i=10;i>0;i--)
  {
    x*=i;
  }
  std::cout << ｘ << std::endl;
  return 0;
}

まあ、このくらいなら正直どちらでも変わらない気もします。

しかし、処理内容によっては普通にループを書くより再帰関数にした方が圧倒的に簡潔なので、使いこなせることが好ましいテクニックです。

Pietで再帰関数

この程度なら難しくはありません。¹

まずは方針を決めます。

フラグ0と階乗を計算する値をプッシュしておく
〜ループ開始1〜
直前にプッシュした値から1を引いた値をプッシュする
フラグ1をプッシュし、先ほどの値と順番を入れ替える
先ほどプッシュした値が0でないなら「〜ループ開始1〜」に戻る
最後にプッシュしたフラグと値を削除
〜ループ開始2〜
フラグをチェックして0ならループをぬけ「〜終了処理〜」へ
スタックの最上部にある2つの数値を掛け算する
「〜ループ開始2〜」へ
〜終了処理〜
計算結果を表示し、終了

Pietソースコード

では実際に書いてみます。まずは処理順から。今回は短いのでそのまま載せます。

命令の詳細はこちら。

ymos-hobby-programing.hatenablog.com

push1 dup sub push2 push5 mul
goto:fact

:factR
outn pop end

:fact
dup push1 sub push1 push2 push1 roll
dup dup dup sub gt
if:factN:factMulP

:factN
goto:fact

:factMulP
pop pop

:factMul
push2 push1 roll
if:factMulN:factR

:factMulN
mul goto:factMul

これをGridPietGeneratorで処理した結果がこちら。

GridPietGeneratorについてはこちらの記事を参照。

ymos-hobby-programing.hatenablog.com

コーデル数は51x53と小さめです。

ちゃんとnpietでも動きます。

./npiet -cs 10 factorialx10.png 
3628800

処理解説

では処理の解説です。例によって処理順はコロン「：」で始まる行で区切られており、それぞれが処理のひとかたまりになっています。

ちなみに生成されたソースコードに対応させるとこんな感じです。このように、GridPietGeneratorで生成されたコードは、処理ブロックのカタマリが画像のフチに配置されます。

これらの処理順を図示すると次のようになります。極めてシンプルです。

処理順を解説していきます。

スタックの初期化

まずは「:1」ブロックでスタックを初期化します。

初期化時のスタックの変化は下図の通りです。

灰色部分がスタック（＝データを入れる容器）
文字のついた白い長方形がデータ
スタックのデータ出入り口は上がわ

と考えてください。

最終的にスタックには0と10が積まれます。

下の0はフラグです（後で説明します）
上の10は階乗計算の対象となる数値10です

10, 9, 8, ... と数値をスタックに積んでいく処理

次に:factと:factNの部分です。

この部分では数値1ずつ減らしながらスタックにプッシュしていきます。

具体的なスタックの変化は次のようになります。

スタックには既にフラグfと数値xの組（f、x）がいくつか入っていて、そのうちの最上部の1組だけを表示したのが上の図だと考えてください。

まずは今スタックに入っている値xをコピーして、x-1をスタックにプッシュします。さらに新たにフラグ1をプッシュして順番を入れ替え、初期化の時と同じ順番、つまり、

下がフラグ
上が値

となるようにします。

続いてこの部分で、現在の値x-1が0より大きいか判定します。比較に使う0を作るために、x-1をdup命令で3回も複製し、うち2つを引き算して0をつくっています。

最後の部分は次の判定をif命令で実行しています。

x-1が0より大　→　:factに戻って繰り返す ²
x-1が0　→　次の処理である:factMulPに進む

この部分を繰り返すことで、スタックには、下から、

フラグf(=0)、10、フラグf(=1)、9、...、フラグf(=1)、1、フラグf(=1)、0

と値がプッシュされていきます。フラグを挟んで階乗計算に必要な数列{10, 9, ..., 1}が用意できました。

階乗計算

いよいよ階乗計算です。

まず準備として、:factMulPブロックでは、スタックの最上部の2つの値をポップします。この2つの値は使わないからです。

続いて終了判定と掛け算を繰り返す部分です。:factMulブロックと:factMulNブロックでその処理をしています。

:factMulブロックでは、終了判定を行なっています。まず上2つだけに注目して、roll命令で順番を入れ替えます。フラグがスタックの最上部に来たところで、if命令を使い、

フラグfが1なら継続　→　:factMulNブロックに進む
フラグfが0なら終了　→　:factRブロックに進む（＝ループ脱出）

とします。初期化時や:factブロックでプッシュしていたフラグは、ここで処理順を決めるために使われます。

継続の場合は、:factMulNブロックで、スタック最上部の2数を掛け算します（mul命令）。

上図のスタック変化には、フラグf'のさらに下にあった、フラグf''と数値データx'も表示しています。掛け算の結果、スタック最上部は、

...、フラグf''、数値x'、フラグf'、数値x X

となり、フラグと数値が交互に現れます。このまま:factMulに戻れば、スタックにプッシュされている数値が順々に掛け算されていくという算段です。

ループ終了

掛け算のループは初期化時にプッシュしたフラグ0 に到達すると終了します。このときの:factMulブロックでの処理を見てみましょう。

このときはif命令で、初期化時にプッシュしたフラグfが読み込まれますが、このfの値は0なので:factRブロックに進みます。

ここまででスタックには、計算結果、つまり、10、9、...、1までの全ての数値の積Xのみが格納されています。その結果を:factRブロック内のoutn命令で出力して終わり、となります。³

以上が10の階乗プログラムの説明です。

最後に

「再帰関数」と銘打ちながら、あまり再帰関数らしさが感じられませんでした。正直、階乗の計算ならループでいけますし。。。

さて、前回お話ししていたように、今回はスタックの変化がわかるように図にしてみました。正確にいうと、この図を半自動で作るツールを作り、今回初めて使ってみました。説明の手間も省けますし、見るほうも図があると多少わかりやすいと思うので、自分としてはよかったと思っています。

次回もまた適当にネタを探してPietで実装したいと思います。

ではまた。

とか言ってデバッグに結構時間かかりましたが・・・。↩
厳密には:factNに進みますが、:factNブロックには命令がなく、すぐに:factにジャンプしますので、実質的には:factに進むことになります。↩
ちなみに:factRブロック内にはpop命令もありますが、これは不要でした。すみません。これでも動きはします（スタックに値がないのにポップしようとするので命令が実行されず無視されます。）↩