再帰とジェネレータの組み合わせ

※この投稿はQiitaのテストです。

再帰とジェネレータを組み合わせることでシンプルな構造で再帰を表現できる場合がある。

正規表現の再帰

正規表現で再帰的な括弧の対応を取るのは困難。PHPやRubyでは正規表現に専用の構文があるがPythonにはない。
再帰関数を使うことでかなり簡単に括弧の対応が取れる。

import re
prog = re.compile(r"\((.+)\)")

def rec_search(s):
    "丸括弧を再帰的に取得してリストで返す"
    match = prog.search(s)
    r = []
    if match:
        r.append(match)
        for i in rec_search(match.group(1)):
            r.append(i)
    return r

リストを作成して呼び出し元に返すようにしている。ちょっと見た目が汚い。

ジェネレータと組み合わせる

import re
prog = re.compile(r"\((.+)\)")

def recsearch(s):
    "丸括弧を再帰的に取得してイテレートする"
    match = prog.search(s)
    if match:
        yield match
        for i in rec_search(match.group(1)):
            yield i

相当シンプルになった。値をyieldしたらその値を捨ててしまって良いので簡単になる。
注意するとこはrec_searchはジェネレータなので呼び出し元に返すようにyieldすること。そうしないとなにもしない関数呼び出しが発生して終了してしまう。

実行結果

>>> for i in rec_search("(1 + (1 + 2))"):
    print(i)

<_sre.SRE_Match object; span=(0, 13), match='(1 + (1 + 2))'>
<_sre.SRE_Match object; span=(4, 11), match='(1 + 2)'>

yield fromでさらにシンプルにする

python3.3で登場した。yield fromで指定したジェネレータ関数を実行して結果が全て返るまで呼び出し元で待つ。
上記の関数のyiled from使用版。

import re
prog = re.compile(r"\((.+)\)")

def rec_search(s):
    "丸括弧を再帰的に取得してイテレートする"
    match = prog.search(s)
    if match:
        yield match
        yield from rec_search(match.group(1))

さらに短くシンプルになった。

ファイル名を再帰で取得する

import os

def iter(dirctory):
    "directory以下全てのファイルをイテレートする"
    d = os.listdir(dirctory)
    if d:
        for f in (os.path.join(dirctory, f) for f in d):
            if os.path.isfile(f):
                yield f
            elif os.path.isdir(f):
                yield from iter(f):

os.listdir関数だけ使って再帰的に取得する例。
ファイルかフォルダかを判定してフォルダならもう一度再帰呼び出しをしている。

おわり

最近再帰を覚えていろいろとやってみた。
正規表現は構文解析使った方がいいしファイル名の取得はpathlib.Path().globで出来るのであんまし実用性はない…。