発展：再帰でえがく

第 13 章で関数を作れるようになり，第 14 章で return を習いました． このページは，その 2 つを済ませた人へのごほうびです． 関数の使い方をもうひとつだけ覚えると， びっくりするほど短いプログラムで，びっくりするほど複雑な絵が描けます．

その使い方とは，関数の中から，その関数自身を呼ぶというものです． これを再帰（さいき，recursion）といいます． はじめて聞くと「そんなことをして大丈夫なのか」と思うでしょう． 大丈夫です．ただしひとつだけ守らなければならない約束があります． それが何かも，このページで説明します．

タートルグラフィックスと再帰は，とても相性のよい組み合わせです． 木・雪の結晶・海岸線・シダの葉など，自然界にある 「一部を拡大すると全体と同じ形が出てくる」かたちが， 数行のプログラムで描けてしまいます． 少し進んだ内容ですが， ここまで進んだ人なら必ず読めます．

15.1　自分を呼ぶ関数

合わせ鏡を見たことがあるでしょうか． 鏡と鏡を向かい合わせると，鏡の中に鏡が映り， その鏡の中にもまた鏡が映って，奥へ奥へと続いていきます．

身のまわりには，こういう「中に自分と同じものが入っている」 かたちがたくさんあります．

• 合わせ鏡　鏡の中に，鏡が映っている．
• マトリョーシカ（入れ子人形）　人形を開けると，ひとまわり小さい人形が出てくる．それを開けると，また小さい人形が出てくる．
• フォルダ　フォルダの中にフォルダがあり，その中にもフォルダがある．
• 木の枝　枝の先が分かれて，その先もまた分かれている．小枝だけを見ると，木全体を小さくしたような形をしている．

プログラムでこれを表すと，関数の中で，その関数自身を呼ぶという形になります．

def matryoshka(size):
    # ここで自分自身を呼んでいる
    matryoshka(size - 1)

ただし，これだけでは永遠に止まりません． マトリョーシカにも，いちばん内側の 「もう開かない人形」がありますね． それに当たるものをプログラムにも書かなければいけません． そこが，再帰でいちばん大事なところです．

15.1.1　いちばん小さい例 — カウントダウン

絵はあとにして，まず print だけの，いちばん小さい再帰を見ます． 3 から 1 まで数えて「発射！」と言うプログラムです．

def countdown(n):
    if n == 0:               # 止まる条件
        print("発射！")
        return               # ここで終わり．自分を呼ばない
    print(n)
    countdown(n - 1)         # 1 つ小さくして，自分を呼ぶ

countdown(3)

コンソールに次のように出ます．

3
2
1
発射！

countdown(3) を 1 回呼んだだけなのに， 4 行表示されました．何が起きたのか，順に追ってみましょう．

1. countdown(3)　n は 3．0 ではないので 3 と表示し，countdown(2) を呼ぶ．
2. countdown(2)　2 と表示し，countdown(1) を呼ぶ．
3. countdown(1)　1 と表示し，countdown(0) を呼ぶ．
4. countdown(0)　n が 0 になった．発射！ と表示し，自分を呼ばずに return する．
5. ここから，呼ばれたのと逆の順番に戻っていく．countdown(0) → countdown(1) → countdown(2) → countdown(3) → 本文．

絵にすると次のようになります． 呼ぶたびに右下へ一段ずつ深くなり， 止まる条件にぶつかったところで折り返して， 深いところから順に戻ってくるのが分かります．

15.1.2　「行き」と「帰り」がある

さきほどのプログラムでは，戻ってくるときには何もしていませんでした． countdown を呼んだあとにも命令を書いてみましょう．

def countdown(n):
    if n == 0:
        print("発射！")
        return
    print("行き", n)
    countdown(n - 1)
    print("帰り", n)         # 戻ってきてから実行される

countdown(3)

結果はこうなります．「行き」は 3・2・1 の順，「帰り」は 1・2・3 の順です．

行き 3
行き 2
行き 1
発射！
帰り 1
帰り 2
帰り 3

自分を呼ぶ行より前に書いた命令は「行き」に， あとに書いた命令は「帰り」に実行される． これは絵を描くときにそのまま効いてきます． たとえばあとで出てくる木では， 「行き」で枝を伸ばし，「帰り」でもとの場所まで戻るのに使います．

15.1.3　止まる条件が無いとどうなるか

では，止まる条件（if n == 0: の部分）を消すとどうなるでしょうか． 予想してから，実行してみてください．

# 止まる条件が無い．わざとエラーを出す例

def countdown(n):
    print(n)
    countdown(n - 1)

countdown(3)

3, 2, 1, 0, -1, -2, ... と数がどこまでも減っていき， しばらくして次のエラーで止まります．

RecursionError: maximum recursion depth exceeded

「再帰の深さが限界を超えました」という意味です． 関数を呼ぶたびに，コンピュータは 「どこへ戻ればよいか」「n はいくつだったか」を覚えておく必要があります． 覚えておく場所には限りがあるので， だいたい 1000 回くらい深くなったところで 「もう覚えきれません」と音を上げるのです．

15.2　小さい同じ問題に減らす

再帰をうまく使うコツは， 大きい問題を，同じ形の小さい問題に減らすと考えることです． 自分で全部やろうとしないのがポイントです． ひと手間だけ自分でやって，残りは「小さい自分」に任せるのです．

15.2.1　階乗

階乗とは，1 からその数までを全部かけたものです． 5! = 5 × 4 × 3 × 2 × 1 = 120 のように書きます． ここで，かけ算の後ろのほうをよく見てください．

5! = 5 × 4 × 3 × 2 × 1
          ~~~~~~~~~~~~~
          これは 4! そのもの

つまり 5! = 5 × 4! です．同じように 4! = 4 × 3!， 3! = 3 × 2!…と続き，最後は 1! = 1 で止まります． この 2 行を，そのままプログラムにできます．

# n の階乗を返す
def fact(n):
    if n == 1:               # 止まる条件
        return 1
    return n * fact(n - 1)   # 自分より 1 小さい階乗に任せる

print("3! =", fact(3))
print("5! =", fact(5))
print("10! =", fact(10))

3! = 6，5! = 120，10! = 3628800 と表示されます． fact の中身は 3 行しかありません． 「n が 1 なら 1」「そうでなければ n かける n-1 の階乗」．数学の定義をそのまま書いただけです．

# 1 から n までの合計を返す
def total(n):
    if n == ____:            # 止まる条件
        return 0
    return n + total(____)   # 1 小さい合計に任せる

print("1〜5 の合計:", total(5))
print("1〜10 の合計:", total(10))
print("1〜100 の合計:", ____)

15.3　タートルで描く — やさしいものから

ここからが本題です．まずは，枝分かれしないやさしい図形から始めます． 自分を呼ぶ回数が 1 回だけなら，動きは for とほとんど同じで，追いかけやすいからです．

15.3.1　入れ子の正方形

正方形の中に，ひとまわり小さい正方形．その中にまた小さい正方形． マトリョーシカそのものです．考え方はこうです．

1. 1 辺 size の正方形を描く（これがひと手間）．
2. 少し内側へ入る．
3. ひとまわり小さい入れ子の正方形を，自分に任せる．
4. 入った分だけ戻って，位置と向きを元どおりにする（第 13 章の約束）．
5. ただし size が小さくなりすぎたら，何もしないで終わる（止まる条件）．

from turtle import *

pensize(2)
pencolor("royalblue")
ht()

# 1 辺 size の正方形から始まる入れ子模様を描く
def nest(size):
    if size < 20:            # 止まる条件
        return
    for i in range(4):       # ひと手間：正方形を 1 つ描く
        fd(size)
        lt(90)
    pu()                     # 内側へ 12 だけ入る
    fd(12)
    lt(90)
    fd(12)
    rt(90)
    pd()
    nest(size - 24)          # 残りは小さい自分に任せる
    pu()                     # 入った分だけ戻る
    lt(90)
    bk(12)
    rt(90)
    bk(12)
    pd()

pu()
goto(-100, -100)
seth(0)
pd()
nest(200)

done()

nest(200) と 1 回呼ぶだけで， 200 → 176 → 152 → … → 32 と 8 つの正方形が描かれました． 最後の nest(8) は size < 20 なので，何も描かずに戻ります．

from turtle import *

pensize(2)
pencolor("seagreen")
ht()

# 1 辺 size の正三角形から始まる入れ子模様を描く
def nest3(size):
    if size < ____:          # 止まる条件
        return
    for i in range(3):       # ひと手間：正三角形を 1 つ描く
        fd(size)
        lt(____)
    pu()                     # 内側へ入る
    fd(20)
    lt(90)
    fd(11)
    rt(90)
    pd()
    ____(size - 40)          # 残りは小さい自分に任せる
    pu()                     # 入った分だけ戻る
    lt(90)
    bk(11)
    rt(90)
    bk(20)
    pd()

pu()
goto(-140, -120)
seth(0)
pd()
nest3(280)

done()

15.3.2　渦巻き

次は渦巻きです．「少し進んで，少し曲がって， あとは少し短い渦巻きを描く」．それだけです．

from turtle import *

pensize(2)
pencolor("crimson")
ht()

# 長さ length から始まる渦巻きを描く
def spiral(length):
    if length < 4:           # 止まる条件
        return
    fd(length)
    lt(91)
    spiral(length - 3)       # 少し短い渦巻きは，小さい自分に任せる

spiral(160)

done()

spiral は 53 回自分を呼んでから止まります． この図形は for でも書けます（第 13 章の虫食い 13-C がそれでした）． どちらがよいかは 15.7 節で考えます．

15.4　枝分かれする木

ここからが再帰の本領です． いままでは自分を1 回呼んでいました． 2 回呼ぶと，何が起きるでしょうか．

木を思い浮かべてください．幹があり，先で 2 つに分かれます． 分かれた枝も，その先でまた 2 つに分かれます． 枝 1 本だけを取り出して眺めると， それ自体が小さな木になっています． だから「木を描く」手順はこう書けます．

1. length だけまっすぐ進む（これが幹）．
2. 左を向いて，ひとまわり小さい木を描く（自分に任せる）．
3. 右を向いて，ひとまわり小さい木を描く（もう一度自分に任せる）．
4. 向きを戻し，幹の長さだけ後ろへ下がって元の場所へ帰る．
5. ただし length が短くなりすぎたら，何も描かずに終わる．

from turtle import *

pensize(2)
pencolor("saddlebrown")
ht()

# 幹の長さ length の木を描く（描き終わったら元の位置・向きに戻る）
def tree(length):
    if length < 10:          # 止まる条件
        return
    fd(length)               # 幹を伸ばす
    lt(30)
    tree(length * 0.7)       # 左の枝は，小さい木に任せる
    rt(60)
    tree(length * 0.7)       # 右の枝も，小さい木に任せる
    lt(30)                   # 向きを戻す
    bk(length)               # 元の場所まで下がる

pu()
goto(0, -170)
seth(90)                     # 上を向かせる
pd()
tree(110)

done()

8 行です．fd と lt を 何百個も並べて描いた絵ではありません． 「木とは，幹の先に小さい木が 2 本ついたもの」と書いただけで，この形が出てきます．

枝分かれがどれくらいの速さで増えるかを見てみましょう． 止まる条件を「長さ」ではなく「あと何回分かれるか」に変えて， 深さを指定できるようにします．

# 深さ n の木を描く
def tree(length, n):
    if n == 0:               # あと 0 回なら，もう分かれない
        return
    fd(length)
    lt(30)
    tree(length * 0.7, n - 1)
    rt(60)
    tree(length * 0.7, n - 1)
    lt(30)
    bk(length)

深さを 1 増やすだけで，枝の数はほぼ 2 倍になります． 深さ 2 で 3 本，深さ 4 で 15 本，深さ 7 で 127 本． プログラムは一文字も変えていません．変えたのは数字 1 つだけです．

from turtle import *

pensize(2)
pencolor("darkgreen")
ht()

# 幹の長さ length の木を描く
def tree(length):
    if length < 12:
        ____                 # 自分を呼ばずに終わる
    fd(length)
    lt(25)
    tree(length * ____)      # 左の枝（必ず短くする）
    rt(50)
    tree(length * 0.75)      # 右の枝
    lt(25)                   # 向きを元に戻す
    ____(length)             # 位置を元に戻す

pu()
goto(0, -180)
seth(90)
pd()
tree(100)

done()

15.4.1　枝の太さと色を変える

本物の木は，根元が太くて先が細く，先のほうは緑色です． length の値を見て太さと色を決めれば，そのとおりになります． 引数が 1 つあるだけで，深さに応じた変化が自然につけられるのが再帰のよいところです．

from turtle import *

ht()

# 幹の長さ length の木を描く．細い枝ほど緑にする
def tree(length):
    if length < 8:
        dot(5, "yellowgreen")    # 枝の先に葉をつける
        return
    pensize(length / 12 + 1)     # 根元ほど太く
    if length < 25:
        pencolor("forestgreen")
    else:
        pencolor("saddlebrown")
    fd(length)
    lt(28)
    tree(length * 0.72)
    rt(56)
    tree(length * 0.72)
    lt(28)
    pensize(length / 12 + 1)     # 帰ってきたら太さと色を設定し直す
    if length < 25:
        pencolor("forestgreen")
    else:
        pencolor("saddlebrown")
    bk(length)

pu()
goto(0, -180)
seth(90)
pd()
tree(120)

done()

15.5　コッホ曲線とコッホ雪片

次はコッホ曲線です．考え方はとても単純で， 1 本の線を 4 本に置き換える，それだけです．

1. まっすぐな線を 3 等分する．
2. 真ん中の 1 つを取り去って，かわりにそこへ山（正三角形の 2 辺）を立てる．
3. できた 4 本の線それぞれに対して，同じことをする．

プログラムにするとこうなります． 「線 1 本」が止まる条件，「4 本に置き換える」が再帰です．

from turtle import *

pensize(2)
pencolor("royalblue")
ht()

# 長さ length，深さ n のコッホ曲線を描く
def koch(length, n):
    if n == 0:               # 止まる条件：まっすぐ引くだけ
        fd(length)
        return
    koch(length / 3, n - 1)  # 1 本目
    lt(60)
    koch(length / 3, n - 1)  # 2 本目（山の左側）
    rt(120)
    koch(length / 3, n - 1)  # 3 本目（山の右側）
    lt(60)
    koch(length / 3, n - 1)  # 4 本目

pu()
goto(-180, -40)
seth(0)
pd()
koch(360, 4)

done()

from turtle import *

pensize(2)
pencolor("darkviolet")
ht()

# 長さ length，深さ n のコッホ曲線を描く
def koch(length, n):
    if n == ____:                # 止まる条件
        fd(length)
        return
    koch(length / ____, n - 1)
    lt(60)
    koch(length / 3, ____)       # 深さを 1 減らす
    rt(____)
    koch(length / 3, n - 1)
    lt(60)
    koch(length / 3, n - 1)

pu()
goto(-180, -30)
seth(0)
pd()
koch(360, 3)

done()

15.5.1　コッホ雪片

コッホ曲線を 3 本，正三角形の形につなぐとコッホ雪片になります． koch はそのまま使い回せます． 第 13 章でやったように，できた部品を組み合わせるだけです．

from turtle import *

pensize(2)
pencolor("steelblue")
ht()

def koch(length, n):
    if n == 0:
        fd(length)
        return
    koch(length / 3, n - 1)
    lt(60)
    koch(length / 3, n - 1)
    rt(120)
    koch(length / 3, n - 1)
    lt(60)
    koch(length / 3, n - 1)

# コッホ曲線 3 本で雪片を作る
def snowflake(length, n):
    for i in range(3):
        koch(length, n)
        rt(120)

pu()
goto(-130, 75)
seth(0)
pd()
snowflake(260, 3)

done()

snowflake 自身は再帰ではありません．ただの for です． 再帰の関数を，ふつうの関数の中から部品として使う． これができると，作れる絵が一気に広がります．

15.6　シェルピンスキーの三角形

最後はシェルピンスキーの三角形です． これも考え方は 1 行で言えます． 「大きい三角形とは，半分の大きさの三角形が 3 つ集まったもの」． 左下・右下・上の 3 か所に，半分の三角形を置くだけです．

移動には，第 13 章で作った jump（線を引かずに動いて，向きは元に戻す）を使います． 三角形の 1 辺の長さが size のとき， 左下 → 右下は「右へ size/2」， 右下 → 上は「左斜め上（120 度）へ size/2」， 上 → 左下は「左斜め下（240 度）へ size/2」です．

from turtle import *

pensize(1)
pencolor("crimson")
ht()

# 線を引かずに移動する（向きは元に戻す）
def jump(dist, angle):
    pu()
    lt(angle)
    fd(dist)
    rt(angle)
    pd()

# 1 辺 size の正三角形を描く
def triangle(size):
    for i in range(3):
        fd(size)
        lt(120)

# 1 辺 size，深さ n のシェルピンスキーの三角形を描く
def sierpinski(size, n):
    if n == 0:               # 止まる条件：三角形をひとつ描く
        triangle(size)
        return
    sierpinski(size / 2, n - 1)   # 左下
    jump(size / 2, 0)
    sierpinski(size / 2, n - 1)   # 右下
    jump(size / 2, 120)
    sierpinski(size / 2, n - 1)   # 上
    jump(size / 2, 240)           # 元の場所へ帰る

pu()
goto(-170, -150)
seth(0)
pd()
sierpinski(340, 4)

done()

15.7　再帰と繰り返しの使い分け

ここまで読むと「for はもう要らないのでは」と思うかもしれません． そんなことはありません． for で書けるものは for で書くほうがよいのです．

15.3.2 節の渦巻きは，for でも書けました．見比べてください．

絵は同じです．行数もほとんど変わりません． こういう場合は for のほうが，読む人にとってやさしいプログラムです． for なら RecursionError の心配もありません．

では，再帰でなければ困るのはどんなときでしょうか． 枝分かれするときです． 木を for で描こうとしてみてください． 幹から 2 本，その先からまた 2 本…と， 枝の 1 本 1 本について「いまどこにいて，どちらを向いていたか」を 自分で全部覚えておかなければなりません．とても書けたものではありません．

15.8　深さを増やすと命令数が爆発する

再帰でいちばん驚くのは， 数字を 1 つ増やしただけで，絵の細かさが何倍にもなることです． これは楽しい反面，危険でもあります．

コッホ曲線の深さを 4 から 8 にすると，線の数は 256 本から 65536 本． 256 倍です． 深さ 10 なら百万本を超えます．

15.9　この章で出てきた書き方

演習

どの演習にも出発点となるプログラムが入っています． 「▶ この演習を開く」で右側に読み込み， 各演習の「評価の目安」の必須をすべて満たしてから，発展させて作品にしてください． どの演習でも，止まる条件と自分を呼ぶ行を自分で書くところが入っています． 深さや長さは，小さいほうから 1 つずつ増やして試すこと．

まとめ

• 再帰とは，関数の中からその関数自身を呼ぶこと．合わせ鏡やマトリョーシカのように，中に自分と同じものが入っている形を表せる．
• 再帰関数には必ず止まる条件（ベースケース）を書く．そこでは自分を呼ばない．これが無いと RecursionError になる．
• 自分を呼ぶときは，引数を必ず小さくして，止まる条件へ近づける．
• 呼び出しは積み重なり，止まる条件で折り返して逆順に戻ってくる．自分を呼ぶ行より前が「行き」，あとが「帰り」の処理．
• 考え方は「大きい問題を，同じ形の小さい問題に減らす」．ひと手間だけ自分でやって，残りは小さい自分に任せる．
• タートルでは，元の位置・元の向きに戻す（第 13 章の約束）ことが決定的に大事．再帰関数は，自分で自分を部品として使う関数だから．
• 枝分かれするものは再帰が向く（木・コッホ曲線・シェルピンスキー）．for で書けるものは for で書くほうがよい．
• 深さを 1 増やすと命令数は何倍にもなる．小さい深さから 1 つずつ試すこと．この教材は 12 万命令・10 秒で止まる．

たった 8 行の tree が木になり，10 行の koch が雪の結晶になりました． 短いプログラムが単純な絵しか描けないとは限らないのです． プログラミングのおもしろさは，まさにここにあります．

第 13 章で「関数は部品だ」と学びました． 再帰は，その部品が自分自身を部品として使うという， ひとひねりしただけの考え方です． それだけで，これほど世界が広がります． 気が向いたときに，自分の模様を育ててみてください．

復習：虫食いで確かめる

コードの ____ を埋めてください．実行前に結果を予測し，実行後に問題文の条件と照合しましょう．assert は条件が成り立つかを調べ，成り立たないとエラーになります．

def countdown(n):
    if n ____ 0:
        ____
    print(n)
    countdown(n - 1)
countdown(3)

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(____)
print(sum_to(4))
assert sum_to(4) == 10