2008年11月6日

ジェネレーターと再帰関数って同じ用途に使うことがあったっけかな、と思い、ちょっとメモしておきます。 無限に続くリストを作成するためにジェネレーターを利用することは全くもってその通りですが、同じ用途で再帰関数を使う局面はあまりないような気がします。遅延評価が関係すると事情は異なるかもしれませんが、yield する箇所で遅延させれば全てジェネレーターの範疇に収まりそうです。 再帰関数は、フィボナッチ数列のナイーブな実装に代表されるように、原始的な状態が決まるまで次の状態が決まらない場合に使うことが多いと思います。このため、前の状態が決まるまで評価を遅延させていると考えられます。しかし、無限に続くようなリストを作成することは難しくなります。前の状態を尋ねることが出来るのは、後続の状態だけだからです。100番目の状態を尋ねられるのが 101番目以降の状態だけだとすれば、無限番目の状態を尋ねられるのは何番目でしょうか? という数学の問題になってしまいます。別に、可算無限 / 非可算無限の違いをどうこうということではありません。単に、最後が分からないと評価を開始できない、というだけです。 一方で、ジェネレーターは次の状態が存在するまで原始的な状態を拡張していく方法です。簡単な数の数え上げで考えると、100 の次は 101 で、その次は 102 ... と単調に増加させていくことができます。再帰関数は上界が決まらないと評価が始められないことに対して、ジェネレーターは上界を意識せずに評価を進めることができます。 結局のところ、特性の異なる二つの考え方を渾然一体とするのは危険だと言えそうです。 なんとなくの思いつきですが、Python で再帰関数とジェネレーターの、おそらく一番簡単なサンプルを書いてみました。
# -*- encoding: utf-8 -*-

def rec(query):
    if len(query):
        rec(query[1:])
        print query

def gen(query):
    while len(query):
        yield query[0]
        query = query[1:]

sample = "hoge"
print "\n\tsample query: %s\n" % sample
print "---------------------------------------- "
print " recursive printing... "
rec(sample)
'''
e
ge
oge
hoge
'''

print "---------------------------------------- "
print " generative printing... "
s = ""
for i in gen(sample):
    s += i
    print s
'''
h
ho
hog
hoge
'''
ちなみに、手元の「みんなの Python」(250ページ) には、次のような記述があります。
yield 文と return 文を、一つの関数で使うことはできません。
上記サンプルを書いているときにエラーが出たので読んでみましたが、そりゃそうだ、という話でしたとさ。

1 件のコメント:

Unknown さんのコメント...

「みんなのPython」の方が間違っている気がするのですが。
http://www.python.jp/doc/release/ref/return.html
returnはStopIterationを発行するためのものです。
ジェネレータはあくまで状態を保存するイテレータであると考えたほうがいいと思います。
たとえばN値のフラグ処理なんかもジェネレータで実装すると容易に片付いたりするわけで、その場合は再帰を用いますよ。