Python Language
再帰

備考

1からnまでの数値の合計

nが自然数である1からnまでの数字の合計を調べるには、 1 + 2 + 3 + 4 + ... + (several hours later) + nます。代わりに、私はforループを書くことができます：

n = 0
for i in range (1, n+1):
    n += i

あるいは、再帰と呼ばれる手法を使用することもできます。

def recursion(n):
    if n == 1:
        return 1
    return n + recursion(n - 1)

再帰には上記の2つの方法よりも利点があります。再帰は1から3の合計に対して1 + 2 + 3を書き出すよりも時間がかかりません。 recursion(4)場合、再帰を使用して後方に作業することができます。

関数呼び出し：（4→4 + 3→4 + 3 + 2→4 + 3 + 2 + 1→10）

forループは厳密にforward（1 - > 1 + 2 - > 1 + 2 + 3 - > 1 + 2 + 3 + 4 - > 10）で動作します。時には、反復解は反復解より簡単です。これは、リンクされたリストの逆転を実装するときに明らかです。

再帰の目的、方法、および時期

再帰は、元の関数呼び出しが終了する前に関数呼び出しによって同じ関数が再度呼び出された場合に発生します。例えば、よく知られている数学的表現x! （すなわち階乗演算）。階乗演算は、すべての非負整数に対して以下のように定義されます。

• 数字が0の場合、答えは1です。
• それ以外の場合、答えはその数値とその数値より1の階乗の倍数です。

Pythonでは、階乗演算の単純な実装は次のような関数として定義できます。

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

再帰関数は時々理解するのが難しいかもしれないので、このステップを歩みましょう。式factorial(3)考えてみましょう。この関数呼び出しとすべての関数呼び出しは、新しい環境を作成します 。環境は基本的に、識別子（例えば、 n 、 factorial 、 printなど）を対応する値にマップする単なるテーブルです。どの時点でも、 locals()環境locals()を使用して現在の環境にアクセスできます。最初の関数呼び出しでは、定義される唯一のローカル変数はn = 3です。したがって、印刷locals()は{'n': 3}ます。 n == 3 、戻り値はn * factorial(n - 1)ます。

この次のステップでは、状況が少し混乱するかもしれません。私たちの新しい表現を見て、私はすでにnが何であるかを知っています。しかし、私たちはどのfactorial(n - 1)あるかはまだ分かりません。まず、 n - 1は2評価されます。次に、 2をnの値としてfactorial渡す。これは新しい関数呼び出しであるため、この新しいnを格納するための第2の環境が作成されます。 Aを第1の環境、 Bを第2の環境とする。 Aはまだ存在し、 {'n': 3}に等しくなりますが、 B （ {'n': 2}等しくなります）は現在の環境です。関数本体を見ると、戻り値はn * factorial(n - 1)です。この式を評価せずに、元の戻り式に代入しましょう。これを行うことで、私たちは精神的にBを破棄しているので、それに応じてnを代用することを忘れないでください（つまり、 Bのnへの参照はAのnを使用する n - 1置き換えられます）。さて、元の戻り式は、 n * ((n - 1) * factorial((n - 1) - 1))ます。これがなぜそうであるかを理解するために、少し時間をかけてください。

さて、それのfactorial((n - 1) - 1))部分を評価しましょう。 Aのn == 3 、 1をfactorial渡します。したがって、 {'n': 1}等しい新しい環境Cを作成しています。ここでも、戻り値はn * factorial(n - 1)です。元の返り値の式を以前のように調整したのと同じように、 "元の"戻り式のfactorial((n - 1) - 1))を置き換えましょう。 「元の」表現は、 n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1)))です。

ほぼ完了しました。今、 factorial((n - 2) - 1)を評価する必要があります。今回は0を渡してい0 。したがって、これは1評価されます。さて、最後の置換を実行しましょう。 「元の」戻り式は、 n * ((n - 1) * ((n - 2) * 1))です。元の戻り式がAで評価されることを思い出すと、式は3 * ((3 - 1) * ((3 - 2) * 1))ます。これはもちろん、6と評価されます。これが正解であることを確認するには、 3! == 3 * 2 * 1 == 6 。これ以上読む前に、環境の概念と再帰にどのように適用するかを完全に理解していることを確認してください。

if n == 0: return 1の文if n == 0: return 1ます。これは、再帰を示さないためです。ベースケースは絶対に必要です。 1つもなければ、あなたは無限回帰に陥ります。そうすれば、少なくとも1つの基本ケースがある限り、必要なだけ多くのケースを持つことができます。たとえば、次のように等価的にfactorialを書くことができます。

def factorial(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return n * factorial(n - 1)

また、複数の再帰ケースがあるかもしれませんが、比較的珍しく、精神的に処理するのが難しい場合が多いので、そのケースには入りません。

「並行」再帰関数呼び出しを持つこともできます。例えば、次のように定義されるフィボナッチ数列を考える。

• 数字が0の場合、答えは0です。
• 数字が1の場合、答えは1です。
• それ以外の場合、答えは前の2つのフィボナッチ数の和です。

これは次のように定義できます。

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n - 2) + fib(n - 1)

私はfactorial(3)で行ったようにこの関数を徹底的に実行しませんが、 fib(5)最終的な戻り値は以下の（ 構文的に無効な）式に相当します：

(
  fib((n - 2) - 2)
  +
  (
    fib(((n - 2) - 1) - 2)
    +
    fib(((n - 2) - 1) - 1)
  )
)
+
(
  (
    fib(((n - 1) - 2) - 2)
    +
    fib(((n - 1) - 2) - 1)
  )
  +
  (
    fib(((n - 1) - 1) - 2)
    +
    (
      fib((((n - 1) - 1) - 1) - 2)
      +
      fib((((n - 1) - 1) - 1) - 1)
    )
  )
)

これはもちろん5評価される(1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1)))ます。

さて、いくつかの語彙の用語を取り上げてみましょう。

• テールコールは、単に値を返す前に実行される最後の操作である再帰関数呼び出しです。明らかにするために、 return foo(n - 1)はテールコールですが、 return foo(n - 1) + 1は（最後の演算であるためreturn foo(n - 1) + 1ません。
• テールコール最適化 （TCO）は、再帰関数の再帰を自動的に減らす方法です。
• テールコール除去 （TCE）は、再帰なしで評価できる式へのテールコールの削減です。 TCEはTCOの一種です。

テールコールの最適化は、さまざまな理由で役立ちます。

• インタプリタは、環境によって占有されるメモリの量を最小限に抑えることができます。コンピュータに無制限のメモリがないので、過度の再帰的な関数呼び出しはスタックのオーバーフローにつながります 。
• インタプリタは、 スタックフレームスイッチの数を減らすことができます。

Pythonには、さまざまな理由で実装された TCOの形式はありません。したがって、この制限を打ち負かすためには他の技術が必要である。選択の方法は、ユースケースによって異なります。いくつかの直感では、 factorialとfib定義は、次のように反復コードに比較的簡単に変換できます。

def factorial(n):
    product = 1
    while n > 1:
        product *= n
        n -= 1
    return product

def fib(n):
    a, b = 0, 1
    while n > 0:
        a, b = b, a + b
        n -= 1
    return a

これは通常、再帰を手動で削除する最も効率的な方法ですが、より複雑な関数ではむしろ難しくなります。

もう一つの便利なツールはPythonのlru_cacheデコレータで、冗長な計算の数を減らすために使用できます。

Pythonでの再帰を避ける方法について考えましたが、いつ再帰を使うべきですか？答えは「しばしば」ではありません。すべての再帰関数は繰り返し実行できます。どのようにして行うのかを理解するだけの問題です。ただし、再帰が問題になることは稀です。 Pythonでは、予想される入力が再帰関数呼び出しのかなりの数を引き起こさない場合に再帰が一般的です。

再帰が興味のある話題なら、私はSchemeやHaskellなどの関数型言語を勉強することをお勧めします。そのような言語では、再帰がずっと便利です。

フィボナッチシーケンスの上記の例は、Pythonで定義を適用し、後でlruキャッシュを使用する方法を示していますが、非ベースケースごとに2つの再帰呼び出しを行うため、非効率的な実行時間があります。関数への呼び出しの数はn指数関数的に増加します。
非直感的ではなく、より効率的な実装では、線形再帰を使用します。

def fib(n):
    if n <= 1:
        return (n,0)
    else:
        (a, b) = fib(n - 1)
        return (a + b, a)

しかし、それは数字のペアを返す問題があります。これは、いくつかの関数が本当に再帰からあまり得られないことを強調しています。

再帰を伴うツリー探索

次のツリーがあるとします。

root
- A
  - AA
  - AB
- B
  - BA
  - BB
    - BBA

さて、もし要素の名前をすべて列挙したいのであれば、簡単なforループでこれを行うことができます。我々は、ノードの名前の文字列を返す関数get_name()と、ツリー内の与えられたノードのすべてのサブノードのリストを返す関数get_children()と、関数get_root()をget_root()て、ルートノードを取得します。

root = get_root(tree)
for node in get_children(root):
    print(get_name(node))
    for child in get_children(node):
        print(get_name(child))
        for grand_child in get_children(child):
            print(get_name(grand_child))
# prints: A, AA, AB, B, BA, BB, BBA

これはうまくいっていますが、サブノードが自分自身のサブノードを持っていたらどうなりますか？これらのサブノードにはさらに多くのサブノードがあるかもしれません。これを解決する方法は、再帰の使用です。

def list_tree_names(node):
    for child in get_children(node):
        print(get_name(child))
        list_tree_names(node=child)

list_tree_names(node=get_root(tree))
# prints: A, AA, AB, B, BA, BB, BBA

印刷しないで、すべてのノード名のフラットなリストを返すことをお勧めします。これは、ローリングリストをパラメータとして渡すことで実行できます。

def list_tree_names(node, lst=[]):
    for child in get_children(node):
        lst.append(get_name(child))
        list_tree_names(node=child, lst=lst)
    return lst

list_tree_names(node=get_root(tree))
# returns ['A', 'AA', 'AB', 'B', 'BA', 'BB', 'BBA']

最大再帰深度の増加

可能な再帰の深さには限界があります。これはPythonの実装に依存します。制限に達すると、RuntimeError例外が発生します。

RuntimeError: Maximum Recursion Depth Exceeded

このエラーの原因となるプログラムの例を次に示します。

def cursing(depth):
  try:
    cursing(depth + 1) # actually, re-cursing
  except RuntimeError as RE:
    print('I recursed {} times!'.format(depth))
cursing(0)
# Out: I recursed 1083 times!

再帰深さ制限を変更するには、次のようにします。

sys.setrecursionlimit(limit) 

次のコマンドを実行すると、現在の制限値を確認できます。

sys.getrecursionlimit()

私たちの新しい制限で上記と同じ方法を実行する

sys.setrecursionlimit(2000)
cursing(0)
# Out: I recursed 1997 times!

Python 3.5からの例外は、RuntimeErrorから派生したRecursionErrorです。

テール再帰 - 悪い練習

関数から返されるのは再帰呼び出しだけの場合、末尾再帰と呼ばれます。

末尾再帰を使用して書かれたカウントダウンの例を次に示します。

def countdown(n):
    if n == 0:
        print "Blastoff!"
    else:
        print n
        countdown(n-1)

反復を使用して行うことができる計算は、再帰を使用して行うこともできます。末尾再帰を使って書かれたfind_maxのバージョンです：

def find_max(seq, max_so_far):
    if not seq:
        return max_so_far
    if max_so_far < seq[0]:
        return find_max(seq[1:], seq[0])
    else:
        return find_max(seq[1:], max_so_far)

テイル再帰は、Pythonコンパイラが末尾の再帰呼び出しの最適化を処理しないため、Pythonでは悪い習慣とみなされます。このような場合の再帰的なソリューションは、同等の反復的なソリューションよりも多くのシステムリソースを使用します。

スタックイントロスペクションによるテール再帰最適化

デフォルトでは、Pythonの再帰スタックは1000フレームを超えることはできません。これは、より速いsys.setrecursionlimit(15000)を設定することによって変更できますが、このメソッドはより多くのメモリを消費します。代わりに、スタックイントロスペクションを使用してテール再帰問題を解決することもできます。

#!/usr/bin/env python2.4
# This program shows off a python decorator which implements tail call optimization. It
# does this by throwing an exception if it is it's own grandparent, and catching such 
# exceptions to recall the stack.

import sys

class TailRecurseException:
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs

def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
  
This function fails if the decorated
function recurses in a non-tail context.
"""
      
    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException, e:
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func

再帰関数を最適化するために、 @tail_call_optimizedデコレータを使用して関数を呼び出すことができます。上記のデコレータを使用した一般的な再帰の例をいくつか示します。

事例：

@tail_call_optimized
def factorial(n, acc=1):
  "calculate a factorial"
  if n == 0:
    return acc
  return factorial(n-1, n*acc)

print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.

フィボナッチ例：

@tail_call_optimized
def fib(i, current = 0, next = 1):
  if i == 0:
    return current
  else:
    return fib(i - 1, next, current + next)

print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.