Python3 での末尾再帰最適化

バージョン3.11以降なら解決

久々に調べてみたら状況が変わっていた？

Python 3.11で末尾再帰が書けるようになる - なんか考えてることとか

結論

Pythonのクロージャで末尾再帰最適化をする。 - tanihito’s blog
Pythonで末尾再帰する - Blanktar

上記を参考に Python3 で書き直してみる。

tail_recursive.py

from functools import wraps

def tail_recursive(func):
  firstcall = True
  params = ((), {})
  result = func

  @wraps(func)
  def wrapper(*args, **kwd):
    nonlocal firstcall, params, result
    params = args, kwd
    if firstcall:
      firstcall = False
      try:
        while result is func:
          result = func(*args, **kwd)  # call fact
          args, kwd = params
      finally:
        firstcall = True
        return result
    else:
      return func

  return wrapper

@tail_recursive
def fact(n, acc=1):
  if n == 0:
    return acc
  else:
    return fact(n-1, acc*n)

print(fact(10))

shell

> python3 tail_recursive.py
3628800

なにが起きているのか？

まずは基礎的なことから。

デコレータ

@tail_recursive により、関数 tail_recursive がデコレータだと指示している。
デコレータとは「飾り付けるもの」。
デコレータは関数を引数に取り、新たな関数を返す。
その新たな関数は内部で、先に渡された関数を呼び出す。
tail_recursive は wrapper を返す。
wrapper は何かしらの飾り付けを伴って内部で func を呼び出す。

@tail_recursion
def fact(n, acc=1):
  if n == 0:
    return acc
  else:
    return fact(n-1, acc*n)

上記はこう解釈される。

def fact(n, acc=1):
  if n == 0:
    return acc
  else:
    return fact(n-1, acc*n)

fact = tail_recursive(fact)

左辺の fact は wrapper である。

クロージャ

wrapper は tail_recursive のローカル変数を参照している。
Python はこの挙動をサポートしている。これをクロージャという。
nonlocal により、そのローカル変数は更新可能になる。

functools.wraps

@wraps(func) をコメントアウトし、
スクリプトの最後で print(fact.__name__) とすると、出力結果が wrapper になる。
いやいや fact と出力してくれよ、それが wraps の役割だそうな。
要するに func のメタ情報を引き継いでくれというものらしい。

関数 fact を実行すると

デコレータにより、今や fact は wrapper なのであった。

fact(0)
=> wrapper(0, {}) # 1st call
( start while )
=> result = fact(0, {})
-> result = acc
-> result = 1
( end while )
=> 1 # finally

fact(1)
=> wrapper(1, {}) # 1st call
( start while )
=> result = fact(1, {})
-> result = wrapper(0, 1, {}) # 2nd call
-> result = fact
-> result = fact(0, 1, {}) # params load
-> result = acc
-> result = 1
( end while )
=> 1 # finally

fact(2)
=> wrapper(2, {}) # 1st call
( start while )
=> result = fact(2, {})
-> result = wrapper(1, 2, {}) # 2nd call
-> result = fact
-> result = fact(1, 2, {}) # params load
-> result = wrapper(0, 2, {}) # 3rd call
-> result = fact
-> result = fact(0, 2, {}) # params load
-> result = acc
-> result = 2
( end while )
=> 2 # finally