Python独学ノートの関数3——再帰関数

さいきかんすう
関数の内部で、他の関数を呼び出すことができます.関数が内部で自分自身を呼び出す場合、この関数は再帰関数です.
例えば、関数fact(n)で計算階乗nを表す!=1 x 2 x 3 x 4 x ... xnのプロセスは、
fact(n) = n! = 1 x 2 x 3 x 4 x ... x n = (n-1)! x n = fact(n-1) x n
したがって,fact(n)はn x fact(n−1)と表すことができ,n=1の場合のみ特殊な処理が必要である.
そこでfact(n)を再帰的に書くと、

def fact(n):
    if  n==1:
        return 1
    return n * fact(n - 1)

fact(5)を計算すると、関数定義カードに基づいて次の計算プロセスに進むことができます.
===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120
再帰関数の利点は定義が簡単で,論理がはっきりしていることである.理論的には,すべての再帰関数はループの方式と書くことができるが,ループの論理は再帰的にはっきりしていない.
再帰関数を使用するには、スタックオーバーフローの防止に注意する必要があります.コンピュータでは、関数呼び出しはスタック(stack)というデータ構造によって実現され、1つの関数呼び出しに入るたびにスタックにスタックフレームが追加され、関数が戻るたびにスタックフレームが減少する.スタックの大きさが無限ではないので(なぜ?)したがって、再帰呼び出しの回数が多すぎると、スタックがオーバーフローします.fact(1000)がオーバーフローする場合:

>>> fact(1000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in fact
  ...
  File "<stdin>", line 4, in fact
RuntimeError: maximum recursion depth exceeded

再帰呼び出しスタックオーバーフローを解決する方法は,テール再帰最適化により,事実上テール再帰とループの効果は同じであるため,ループを特殊なテール再帰関数と見なすことも可能である.
テール再帰とは、関数が返されると、自分自身が呼び出され、return文に式が含まれないことを意味します.これにより、コンパイラまたは解釈器は、再帰自体が何度呼び出されても、スタックフレームが1つしか使用されず、スタックオーバーフローが発生しないように、テール再帰を最適化することができる.
上のfact(n)関数はreturn n*fact(n−1)が乗算式を導入したため,テール再帰ではない.最後の再帰方式に変更するには、複数のコードが必要です.主に、各ステップの積を再帰関数に入力します.

def fact(n):
    return fact_iter(1, 1, n)
def fact_iter(product, count, max):
    if count > max:
        return product
    return fact_iter(product * count, count + 1, max)

見えますreturn fact_iter(product*count,count+1,max)は再帰関数自体のみを返し、product*countとcount+1は関数呼び出し前に計算され、関数呼び出しに影響しません.
このときfact(5)に対応するfact_iter(1,1,5)の呼び出しは次のとおりです.
===> fact_iter(1, 1, 5)
===> fact_iter(1, 2, 5)
===> fact_iter(2, 3, 5)
===> fact_iter(6, 4, 5)
===> fact_iter(24, 5, 5)
===> fact_iter(120, 6, 5)
===> 120
最後の再帰呼び出しの場合、最適化を行った場合、スタックは増加しないため、何度呼び出してもスタックオーバーフローは発生しません.
残念なことに、多くのプログラミング言語はテール再帰に対して最適化されておらず、Python解釈器も最適化されていないため、上のfact(n)関数をテール再帰方式に変更してもスタックオーバーフローを招く.
ソースコードを参照するために、テール再帰最適化用のdecoratorがあります.
http://code.activestate.com/recipes/474088-tail-call-optimization-decorator/
後でdecoractorの作成方法について説明します.今、この@tail_を使うだけです.call_optimizedでfact(1000)をスムーズに算出できます.
小結
再帰関数を使用する利点は、論理が単純で明確であることであり、深すぎる呼び出しがスタックオーバーフローを引き起こすという欠点がある.
テール再帰最適化のための言語は、テール再帰によってスタックオーバーフローを防止することができる.テール再帰は事実上ループと等価であり,ループ文のないプログラミング言語は再帰のためにループを実現するしかない.
Python標準の解釈器はテール再帰を最適化せず,どの再帰関数にもスタックオーバーフローの問題がある.