記事: 部長
パソコンで、沢山の枝のはった木を自動で描いたり、パズルゲームの全探索をしたりするにはどんなプログラムをかけばいいだろう?
実は、こういった一見複雑で面倒そうな処理が、再帰というプログラム手法を使うとすごく簡単にできたりするので驚きだ。
ここでは、その再帰プログラムについて説明する。
まず、1からnまでの和を求める関数の例だ。
言語はPyrhon。
1 2 3 4 5 6 7 |
def sum(n): if n > 0: return n + sum(n-1) else: return 0 # test print(sum(10)) |
出力結果
1 |
55 |
ポイントは、
1. 関数sumの中でsumが呼ばれている
2. sumの引数が、中ではn-1になっている
3. sumを呼ばない条件がある
だ。
何が起きているのだろう。
以下のように、出力を繋げると、分かりやすいだろう。
1 2 3 4 5 6 7 8 |
def joint(n): if n > 0: return (n, joint(n-1)) else: return 0 # test print(joint(5)) |
出力
1 |
(5, (4, (3, (2, (1, 0))))) |
入れ子のように関数が次々と呼ばれ、
nが0になると止まるのだ。
さて、この再帰を使って図形を描くともっと面白い。