キャパカリオンでもわかるプログラミング講座（心）

このブログが更新されている頃は、まだシャッフル麻雀をやっているのでしょうか。

登山もあるんだから早く寝なきゃダメだゾ！

キャパカリオン講座の最終回、始まります。

無限ループって怖くね

突然ですが皆さん、思考の無限ループに陥ることってありませんか？

私はよくあります。

例えば夜、次のブログのネタを考えているとき、ちょっと気を抜いてると

次のブログは「～」について書こう！」・・・って考えてたことについて書こう！」・・・って考えてたことについて書こう！」・・・

みたいになりませんか？

これがなかなか抜け出せなくて、

ついて書こう！」・・・って考えてたことについて書こう！」・・・あーやめやめ。こんなくだらんこと考えてないで寝よ。。。。。。」って考えてたことについて書こう！

ってぶり返してくるもんですからたちが悪い。

こういうの歌でもよくありますよね。

この手の曲で私が好きなのは、歌謡曲の「あんたがたどこさ」です。

あんたがたどこさ　肥後さ　肥後どこさ　熊本さ　熊本どこさ　船場さ
船場山には狸がおってさ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
・
・
・

あれ、無限ループって怖くね？

まあ本当の歌詞は、

あんたがたどこさ　肥後さ　肥後どこさ　熊本さ　熊本どこさ　船場さ
船場山には狸がおってさ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
それを木の葉でちょいとかぶせ

と終わるんですが、"それを"の音程とリズムが3行目と4行目で同じなのでこうしたループに陥るわけです。

ちなみにこの無限ループ、絵にすると恐ろしいです。

おわかりいただけただろうか・・・

あんたがたどこさジェネレータ

この繰り返し構造をどうやったらプログラムで作れるでしょうか。

一番単純なのはベタ打ちですね。

print("あんたがたどこさ　肥後さ　肥後どこさ　熊本さ　熊本どこさ　船場さ")
print("船場山には狸がおってさ")
print("1回目はじめ")
print("それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ")
print("1回目おわり")
print("2回目はじめ")
print("それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ")
print("2回目おわり")
print("3回目はじめ")
print("それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ")
print("3回目おわり")
print("4回目はじめ")
print("それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ")
print("4回目おわり")
print("それを木の葉でちょいとかぶせ")

さて、もう皆さんは関数を知っているわけですからもう少しスマートに書いてみましょう。

def hunter(count):
    print(str(count)+"回目はじめ")
    print("それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ")
    print(str(count)+"回目おわり")

print("あんたがたどこさ　肥後さ　肥後どこさ　熊本さ　熊本どこさ　船場さ")
print("船場山には狸がおってさ")
hunter(1)
hunter(2)
hunter(3)
hunter(4)
print("それを木の葉でちょいとかぶせ")

ただ、もうこのベタ打ちだとちょっとむずむずしませんか？

だって皆さんはfor文を知っているわけですから。

max_count = 4
def hunter(count):
    print(str(count)+"回目はじめ")
    print("それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ")
    print(str(count)+"回目おわり")

print("あんたがたどこさ　肥後さ　肥後どこさ　熊本さ　熊本どこさ　船場さ")
print("船場山には狸がおってさ")
for count in range(1,max_count+1): #1~4まで
    hunter(count)
print("それを木の葉でちょいとかぶせ")

では、for文以外にどんな書き方ができるでしょうか。

プログラムをかじったことがある人はwhile文があることに気づくでしょう。

while文とは、

while(条件):
    処理

という書式で、条件がTrueの間は処理をし続けるというものです。

つまり、

max_count = 4
def hunter(count):
    print(str(count)+"回目はじめ")
    print("それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ")
    print(str(count)+"回目おわり")

print("あんたがたどこさ　肥後さ　肥後どこさ　熊本さ　熊本どこさ　船場さ")
print("船場山には狸がおってさ")
count = 1
while(count <= max_count): # count <= 4がTrueの間は繰り返す
    hunter(count)
    count += 1 # countを１ずつ上げていく
print("それを木の葉でちょいとかぶせ")

とやればできそうですね。

でも、今回の主役はwhile文ではありません。

実はもう一つこのループ構造を作り出す方法があります。

それこそが本日の主役である再帰関数です。

再帰関数

再帰関数というだけあって関数を使ったテクニックです。

その前に今一度、関数のおさらいです。

関数の基本はジャンプです。

関数が呼ばれたら、関数が定義しているところまで飛んで、中身を全部実行し終えたら、元の行に戻ってきます。

これはもう絵を見てもらったほうが早いので、黄色字のstartからendまでプログラムがどの順番で実行されるか、目で追ってみてください。

ここまではOKですね。

では、ここでちょっと考えてみてください。

関数の中でもう一度自分の関数が呼ばれたらどうなるでしょうか？

関数の基本がジャンプだということを念頭に考えてみると・・・

あれ、無限ループって怖くね？

そうなんです。関数をうまく使えばループ構造を作ることができるのです。

自らの関数の中で再び自らの関数に帰ってくるので、こういう構造の関数を再帰関数と呼びます。

ただ、このままだと無限ループしてしまって困るので、次のような構造を考えてみましょう。

max_count = 2

def hunter(count):
    print(str(count)+"回目はじめ")
    print("それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ")
    print(str(count)+"回目おわり")
    if count < max_count:
        hunter(count+1)

print("あんたがたどこさ　肥後さ　肥後どこさ　熊本さ　熊本どこさ　船場さ")
print("船場山には狸がおってさ")
hunter(1)
print("それを木の葉でちょいとかぶせ")

さあ、これがどうなっているかわかりますか？

コンピュータちゃんの気持ちになって頭の中で順々に追ってみてください。

わかりやすいようにhunter関数を呼ばれるごとにかき分けてみると、以下のような実行順になっていると思います。

無事、無限ループせず帰ってこれましたね。

このようにあるタイミングで再帰をブロックするような構造を組み込むのが再帰関数の基本的な使い方です。

今回はここまで理解してくれれば目標達成です。

再帰関数の自由度

再帰関数のメリットはその自由度の高さです。

例えば今回のあんたがたどこさジェネレータでいえば、for文でもwhile文でも、

n回目はじめ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
n回目おわり

の3行は必ずセットでプリントされます。

もし、

1回目はじめ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
2回目はじめ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
3回目はじめ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
4回目はじめ
それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ
4回目おわり
3回目おわり
2回目おわり
1回目おわり

みたいな出力を実現したい場合は、

max_count = 4
def hunter_start(count):
    print(str(count)+"回目はじめ")
    print("それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ")

def hunter_end(count):
    print(str(count)+"回目おわり")

for count in range(1,max_count+1): #1~4まで
    hunter_start(count)
for count in range(1,max_count+1)[::-1]: #1~4まで逆順
    hunter_end(count)

のようにfor文を２つ書くよりほかありません。

一方で再帰関数ではどうかというと,

max_count = 4

def hunter(count):
    print(str(count)+"回目はじめ")
    print("それを猟師が鉄砲で撃ってさ　煮てさ　焼いてさ　食ってさ")
    if count < max_count:
        hunter(count+1)
    print(str(count)+"回目おわり")

hunter(1)

再帰させるタイミングを変えるだけで簡単に実装できます。

つまりfor文やwhile文よりもはるかに高度なループ構造を作ることができるのです。

では、ではですよ。

もしこんな書き方をしたらどうなりますか？

N = 5
def for_cycle():
    for i in range(N):
        for_cycle()

for_cycle()

え～っと、for_cycle関数の中にfor文があって、for文の中でfor_cycle関数に再帰しているってことは。。。

あーーーー！！！！

N = 5
for i in range(N):
    for i in range(N):
        for i in range(N):
            for i in range(N):
                for i in range(N):
                    for i in range(N):
                        for i in range(N):
                            for i ... 無限ループって怖くね？

と等価ジャン！（白々しい）

あとは適切な再帰をブロックする構造を作ってあげれば、任意の深さのforループネストを実現できそうですね。

それでは、password総当たりプログラムの模範解答です。

#桁数
max_digit = 8
#文字の候補と数
candidates = 'abc'

#再帰関数の定義
def for_cycle(password, digit):
    #a,b,cについてforループ
    for char in candidates:
        #もしmax_digitにまで達していたら
        if digit == max_digit:
            #max_digit-1桁目までの文字列に今回の分を連結したものをプリント
            print(password+char)
        #まだmax_digit未満だったら
        else:
            #digit-1桁目までの文字列に今回の分を連結したものを次の桁に託す
            for_cycle(password+char, digit+1)
    
#関数の実行
for_cycle('',1)

前回の最大限改良したバージョンでも'abc'の8桁では、0.038秒くらいでした。

一方でこの方法だと0.004秒。

速いですね。

人をダメにする言語 python

最後にpythonがなぜこんなにも流行っているかお示ししますね。

import itertools

digit_count = 8
candidate = 'abc'
for i in itertools.product(candidate,repeat=digit_count):
    print("".join(i))

はい、これだけです。今までさんざん苦労してきたことがこれだけでできちゃいます。

ほんと、ひとをダメにする言語ですね。python。

おわりに

ということで、今回でキャパカリオンシリーズは終了です。無事パスワードまでたどり着けたので良かったです。

序破急ならぬ序石皮クヨ心にしてしまったがために、終わりがあるせいで一回の記事が長くなりすぎたのが反省ですね。

次からは細々とやっていきたいと思います。

次の題材なににすっかな～。