Python再帰アルゴリズムの詳細

Python再帰アルゴリズムの詳細
2018.08.05 17:50 1296ブラウズ
再帰の概念は簡単で、関数に自身の呼び出しが含まれている場合、その関数は再帰的です.
再帰(Recursion)とは、数学やコンピュータ科学において、関数の定義において関数自体を用いる方法である.
再帰を使用する場合は、次の点に注意してください.
再帰とは、プロシージャまたは関数で自身を呼び出すことです.
再帰出口と呼ばれる明確な再帰終了条件が必要である.
注意:関数の無限呼び出しを避けるために、再帰出口を忘れないでください.
基本手順の再帰
各再帰プログラムは同じ基本手順に従います. 
1.アルゴリズムを初期化します.再帰プログラムには、通常、開始時に使用されるシード値(seed value)が必要です.このタスクを完了するには、パラメータを関数に渡すか、非再帰的なエントリ関数を指定しますが、再帰計算のシード値を設定できます. 
2.処理する現在の値がベースライン条件と一致しているかどうかを確認します.一致する場合は、処理を行い、値を返します. 
3.答えを再定義するには、より小さなサブ問題またはより簡単なサブ問題(または複数のサブ問題)を使用します. 
4.サブ問題に対してアルゴリズムを実行する. 
5.結果を答えの式にマージします. 
6.結果を返します.
 
ベースライン条件(base case).ベースライン条件は再帰プログラムの最下層位置であり,この位置では操作を行う必要がなく,直接結果を返すことができる.すべての再帰プログラムは、少なくとも1つのベースライン条件を有し、最終的にベースライン条件に達することを確認する必要があります.そうでない場合、プログラムはメモリまたはスタックスペースが不足するまで永遠に実行されます.
主な応用範囲
再帰アルゴリズムは、一般的に3つの問題を解決するために使用されます.
(1)データの定義は再帰的に定義される.(例えばFibonacci関数)
(2)問題解法は再帰アルゴリズムで実現する.(遡及)
(3)データの構造形式は再帰的に定義される.(例えば、木の遍歴、図の検索)
典型的なアルゴリズム
数学やコンピューター科学、プログラミング関連の本を学んだ人の多くは、階乗に出会うに違いない.
n! = 1 × 2 × 3 × … × n
再帰的に定義することもできます.
n! = (n-1)! × n
ここで、n>=1であり、0!=1.
単純で明瞭であるため、再帰的な例としてよく用いられる.
PS:階乗以外にも再帰的に処理できるアルゴリズムがたくさんあります.例えば、フィボナッチ数列、ハンノタワーなどです.
 
非再帰的実装

def factorial(n):
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

階乗関数の再帰的実装

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

再帰プロセス
再帰手順を明確にするために、5!プロセスの分解:

factorial(5)                        #   1       5
5 * factorial(4)                    #   2       4
5 * (4 * factorial(3))              #   3       3
5 * (4 * (3 * factorial(2)))        #   4       2
5 * (4 * (3 * (2 * factorial(1))))  #   5       1 
5 * (4 * (3 * (2 * 1)))             #    5      
5 * (4 * (3 * 2))                   #    4      
5 * (4 * 6)                         #    3     
5 * 24                              #    2      
120                                 #    1      

 
やはりこの関数factorial(N)ですが、N=999とN=1000を試してみましょう.問題が来て、N=999で正解を出力できますが、N=1000では次のエラーが発生します.
RuntimeError: maximum recursion depth exceeded
そこで、デフォルトのPythonには、コンピュータのメモリが消費されないように、再帰的な深さの制限があることを覚えておいてください.デフォルトは1000です.　
再帰的なメリットとデメリット
メリット:
再帰的にコードをよりきれいに、優雅に見せる
複雑なタスクを再帰的により簡単なサブ問題に分解できます.
いくつかのネストされた反復を使用するよりも再帰を使用する方が簡単です
 
欠点:
再帰的なロジックはデバッグ、フォローしにくい
再帰アルゴリズム解題の実行効率は低い.再帰呼び出しの過程で,システムは各層の戻り点,局所量などにスタックを開いて格納する.再帰回数が多すぎるとスタックオーバーフローなどが起こりやすい.
ソース:https://www.imooc.com/article/50223
https://m.pythontab.com/article/1234