FP:再帰で分けて積み上げずに後ろから進もう
このワークシートはMath by Codeの一部です。
これまで、FPシリーズとして、
OOPのデザインパタンの純粋関数型への移植から始めた。
そして、データを載せるコンテナとしてのリスト、辞書を扱ったね。
その次に道具としてのモジュール、operator,functools,itertoolsと進んできた。
今回は趣向を変えて、プログラミングの発想・記法である再帰を扱おう。
１．再帰は発想と記法でツールではない。
再帰は発想と記法であり、ツールではない。
再帰recursionは自己参照で、反復itelateと対照的な意味で扱われる。
itertoolsは生真面目な顔をして堂々とさぼるのが上手なyield,genetatorを部品とするレイジー関数たちがバケツリレーで役立つ世界を作ってくれていた。
再帰は、道具というよりは、もっと広く、深い。
再帰は、発想であり、記述の特徴だ。
たとえば、reduceというドミノ倒し関数がfunctoolsにあったが、
累乗、階乗、累加という発想自体は再帰的と言える。
reduceでは初期値とラムダ式があったように、
端っこと変化方法のペアがないと
無限に続いてしまう。
再帰関数は終了条件baseと再帰式recursionがある。
やはり、端っこと変化方法がペアになっている。
しかし、再帰関数のよくある例は階乗、フィボナッチ数列くらいだ。
苦労して学んでも、例が乏しい本が多い。
再帰はふつうにやると、
スタックの山ができて、いつも１から計算するため計算の山ができる。
それを避けるためのわざは、
パッケージFunctoolsのlru_cacheやcashというデコレタを頭につけるメモ化があった。
他にもforループ回しに直す方法があるが、スタックの山がパンクしたりはしないが、メモリは食うので、スピードに課題がある。
そこに現れる救世主はTCO（末尾呼び出し最適化）だ。
しかし、残念ながらPythonという言語は裏でTCOに変換してくれないので、自力でかかないといけない。
ということで、これからやるのは、
２．発想としての再帰
３．TCOにしてスタックがパンクしない方法
このあたりを探ってみよう。
２．発想としての再帰
発想としての再帰
＜累乗を再帰的に計算する＞
２の10乗の計算は2の5乗の2乗です。
２の5乗は２の4乗の2倍です。
２の4乗は２の2乗の2乗です。
このように、指数が偶数なら半分にして計算したものの2乗
指数が奇数なら1個取って偶数乗にする。
こうすれば、計算が速くなることは経験でわかります。
これをコードにしてみよう。
def fastexp(a: int, n: int) -> int:
if n == 0:
return 1
elif n % 2 == 1:
return a * fastexp(a, n - 1)
else:
t = fastexp(a, n // 2)
return t * t
fastexp(2, 100)#1267650600228229401496703205376
計算は一瞬で終わります。
＜整数の和を再帰的に定義する＞
自然数とはペアノの公理から１から始まる後続者です。
aの前の数をP(a),aの後の数をS(a)とかくと、
add(a,b)=｛a≠0ならadd(P(a),S(a))、a=0ならb｝と定義します。
たし算という計算を自然数のシフトとして再定義できるわけですね。
def add(a: int, b: int) -> int:
if a == 0:
return b
else:
return add(a - 1, b + 1)
add(999,1001)#2000
再帰的な定義の守備範囲は広そうですね。
＜再帰構造を再帰で調べる＞
たとえば、2分木TreeNodeがあり、木の生成は（値value、左left、右right）とかき、
入れ子ができるします。これを中置方式で、左、値、右の順に
走査するときは、中置再帰走査inorder_traversalして結果を出力します。
木の構造に合わせて、左走査＋値＋右走査という順に分解して掘り下げればいいね。
再帰構造には再帰関数、当然といえば当然でした。
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def inorder_traversal(node):
if node is None:
return [] # Base case: return an empty list if the node is empty.
return inorder_traversal(node.left) + [node.value] + inorder_traversal(node.right)
# 木のデータ:
# 10
# / ＼
# 5 15
# / ＼
# 12 20
root = TreeNode(10,
TreeNode(5),
TreeNode(15, TreeNode(12), TreeNode(20)))
result = inorder_traversal(root)
print("走査結果:", result)#走査結果: [5, 10, 12, 15, 20]
＜ソートの王者も再帰的＞
速いソートいえばクイックソートアルゴリズムですね。
スタートとなるリストlstがあります。
適当な軸となる要素pivotをリストからとります。
それより小さい要素群Lと残りGにわけます。
つまり、lst=L+pivot+Gでやめたら、第一段階の並べ替えができます。
しかし、こうかくと次につながりません。
次は、LとGそれぞれスタートとしたいので、
quicksort(L)+pivot+quicksort(G)を返し、ピボットだけか空のリストが終了条件です。
def quicksort(lst):
if len(lst) <= 1:
return lst # Base case: 対象サイズが１以下
else:
pivot = lst[0]
less = [x for x in lst[1:] if x < pivot]
greater_or_equal = [x for x in lst[1:] if x >= pivot]
return quicksort(less) + [pivot] + quicksort(greater_or_equal)
#例
unsorted_list = [3, 9, 30, 90, 7, 10, 1]
sorted_list = quicksort(unsorted_list)
print("クイックソート:", sorted_list)#クイックソート: [1, 3, 7, 9, 10, 30, 90]
＜振り返り＞
いくらでも、例が作れそうです。このくらいにしておきます。
再帰的とは、対象を分割することで、処理対象のサイズをどんどん小さくする。
そして、小さくしたものをくっつけて、巨大な全体を再構成するという発想だといえるね。
シダの葉の細かな仕組みをつかめば、全体をつかんだことになる。
本来フラクタルでないイテラブルな対象でさえ、
フラクタルにとらえる発想ともいえる。
分割統治。
全体を部分と同型に分解することで、
部分を制覇すれば全体が管理できる。
次はTCO、お尻から再帰する方法を見てみよう。
3。TCO（末尾呼び出し最適化TailCallOptimazition）
TCO末尾呼び出し最適化TailCallOptimazition
＜TCOを目指す書き方＞
TCO末尾呼び出し最適化TailCallOptimazition
名前がすごいけど、普通の再帰関数の書き方だと、
計算式の山をつくっておき、結局終了条件という端っことから、
前から順に積んでいく。
この大から小に積んで、小から大に計算するというUターンをやめて、
大から小に順に計算してしまうというストレートなやり方がTCOを「目指す」書き方だ。
階乗計算で記述の発想と表現と効率を比較してみよう。
def fact(n: int) -> int:
if n == 0:
return 1
else:
return n*fact(n-1)
これは、終了条件と再帰式がある由緒正しい再帰だ。
発想も思想もよいけど、スタックを消費する。効率が悪い。
def facti(n: int) -> int:
if n == 0:
return 1
f = 1
for i in range(2, n+1):
f = f * i
return f
これは、スタックがあふれないが再帰とは関係なforループ文だ。
安全をとって、思想を捨てている。
def fact_tail(n, accumulator= 1):
if n==0:
print(f"n={n},accmulator={accumulator}")
return accumulator
else:
print(f"n={n},accmulator={accumulator}")
return fact_tail(n-1, n*accumulator)
fact_tail(10)
[OUT]
n=10,accmulator=1
n=9,accmulator=10
n=8,accmulator=90
n=7,accmulator=720
n=6,accmulator=5040
n=5,accmulator=30240
n=4,accmulator=151200
n=3,accmulator=604800
n=2,accmulator=1814400
n=1,accmulator=3628800
n=0,accmulator=3628800
3628800
これは、分割統治の再帰の発想で、お尻からの累積値をつけたものだ。
効率もよいね。たった、11個の行で10の階乗のステップを確認できた。
しかし、「目指す」書き方ではあるけど、Pythonは内部でスタックに積んでいて
やはりスタックの山はパンクしてします。
なぜか？
import sys
print(sys.getrecursionlimit())
[OUT]
3000になっていました。
だから、print文は無駄な表示をするのでコメントアウトします。
def fact_tail(n, accumulator= 1):
if n==0:
#print(f"n={n},accmulator={accumulator}")
return accumulator
else:
#print(f"n={n},accmulator={accumulator}")
return fact_tail(n-1, n*accumulator)
fact_tail(10)
print(fact_tail(2000))なら、スタックの限界内だから、一瞬で表示します。
しかし、
print(fact_tail(4000))ではスタックの山が高くなりすぎて崩壊します。
残念すぎる。
ではどうする？
＜本当のTCO、呼び出し最適化とは＞
先ほどのTCOを目指すやり方を本当のTCOにします。
つまり、スタックの山を積み上げない方法です。
import sys
# Pythonの文字列表現の限界を10万桁まで拡張する
sys.set_int_max_str_digits(100000)
def factorial_raw(n, accumulator=1):
if n == 0:
return accumulator
else:
return lambda: factorial_raw(n-1, n*accumulator)
def trampoline(thunk):
while callable(thunk):
thunk = thunk()
return thunk
result = trampoline(factorial_raw(4000))
print(f"{len(str(result))} 桁")
print(result)
[OUT]
12674 桁
18288019515140650133147431755739190....................略
スタックに積んだらすぐに下すことを繰り返すので、
山は積みあがりません。
トランポリンという関数はthunkという手形関数を読み込みます。
thunkが呼び出しできる、つまり関数であるうちは読み込み実行します。
しかし、
そうでないとき、
値になったらwhileをぬけて値になったthunkを返します。
だから、トランポリンにfactorial_rawをのっけると、
n==0という端っこにくるまで、引数のない形だけのラムダ式のため、
（n-1, n*accumulator）ここだけが進むのです。
トランポリンがカウンター代わりに値じゃないから次だ。
と進めてくれるからです。
トランポリンには床と空中しかありません。
０階と１階しかないスタックとも言えます。
だから、直進どころか、横滑りして最後の値になってから飛ぶのやめるわけです。
いやあ、だれだか知りませんが、世の中には発想の天才がいるもんですね。
４、振り返り
＜振り返り＞
「再帰」愛のMITの人々やハッカーと
「Python」愛のグイド・ヴァンロッサムの
壮絶は戦いを見ることができた感じがしました。
geogebraのiteration,iterationListはイテレタとして
リカージョン風のことをやるというものです。
イテレタ自体はSequence(式、変数、初期値、終わり、ステップ）という数列があります。
また、zipがあるので、Zip(式、変数１、リスト１、変数２、リスト２）でリスト演算をイテレタなしでできます。
そんな道具箱をもつgeobgebraで、再帰的な発想を深めてみよう。
課題：geogebraでfibonacci以外の再帰関数を作ってみよう。
タイトル「イテレタで再帰もどき」
n=slider(1,170,1)
「iterationListの数列ak+1 がakとkに依存して決められる。」とマニュアルある。
まずは、マニュアル例を普通の階乗計算に直す。
f(k,a)=(k+1) a
factorial = iterationList(f,{1,1},n)
とすると、1,(1+1)1, (2+1)2,......となり、自然数列の積、つまり、階乗数列が出る。
#{1,2,6,24,120,....}
a=factorial(n)
text1="factorial(" + n +")=" + a +""
次に、
g(k)=k+1
h(k,a)=g(k) a
とすることで、kの式の自由度を上げる。
fact2 = iterationList(h,{1,1},n)
はfactorialと同じ動きをすることが確認できる。
i(k,a)=g(k)+ a
とすることで、自然数列の和、つまり、三角数列ができるかも。
triArray=IterationList(i,{1,1},n) #{1,3,6,10,....}
b=triArray(n)
できました。
text2="triangle(" + n +")=" + b +""
今度はaの式を関数にしてコラッツ数列を表示してみよう。
start = Slider(1, 100, 1)
m = Slider(1, 50, 1)
Mod(a,2)がバグるので、floor[a/2:]== a/2として、条件分岐させます。
collaz(a) = If(floor[a/2:]== a/2, a / 2, 3 * a + 1)
collatzArray = IterationList(collaz, start, m)
text3="collaz(" + start+")="+collazArray
１に到達できるかはわかりませんが、スライダーmを動かして見よう。
1にとどかないときはmの設定を少し大きくするなどしてみよう。
お気づきの通り、終了条件のないコラッツ数列なので、１の次は４となり、
1,4,2,の繰り返しをしだすこともわかります。
終了条件がない「再帰もどきのイテレタ」の弱みですね。