Python再帰関数

簡単に述べる
昔は山があって、山の中に寺があって、寺の中にお坊さんがいて、お坊さんに物語を話しています!物語は何ですか.「昔は山があって、山にはお寺があって、お寺にお坊さんがいて、お坊さんに物語を話していました!物語は何ですか?」......
最も古典的な童謡かもしれないが、自然言語の魅力と無限の可能性を十分に示し、永遠にこのような再帰的な方法で続けることができる.の
ロシアの文芸理論家のチャルニシェフスキーは言ったことがある.
芸術は生活に由来するが、生活より高い!
生活はこのようにして、プログラミングの世界もこのようにします-生活の原形あるいは現象がなくて、何がプログラムの創作の源とインスピレーションに来ますか?そこでPythonには,このような関数−再帰関数が現れる.
ほとんどの場合、関数が他の関数を呼び出すのを見ます.これに加えて、関数は自己呼び出しすることもでき、このタイプの関数は再帰関数と呼ばれます.

概要

再帰関数

の典型的なアルゴリズム

反復実装

再帰実装

再帰の長所と短所

詳細参照

一去丶二三里,转载请注明出典:http://blog.csdn.net/liang19890820
さいきかんすう
再帰的な視覚効果の現れ-フレームを持ったモナリザ:
再帰(Recursion)とは、数学やコンピュータ科学において、関数の定義において関数自体を用いる方法である.
再帰を使用する場合は、次の点に注意してください.

再帰は、プロセスまたは関数で自身を呼び出す

である.

は、再帰出口と呼ばれる明確な再帰終了条件を有しなければならない.

注意:関数の無限呼び出しを避けるために、再帰出口を忘れないでください.
典型的なアルゴリズム
数学やコンピューター科学、プログラミング関連の本を学んだ人の多くは、階乗に出会うに違いない.
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
... 
>>> 
>>> factorial(1)
1
>>> 
>>> factorial(5)
120
>>> 
>>> factorial(10)
3628800

開始時、resultは1であり、forループに入り、nまで前の結果にiを乗算する.
再帰的な実装
今、再帰を使って実現し、数学の定義と同じように優雅です.

>>> def factorial(n):
...     if n == 1:
...         return 1
...     else:
...         return n * factorial(n - 1)
... 
>>> 
>>> factorial(1)
1
>>> 
>>> factorial(5)
120
>>> 
>>> factorial(10)
3628800

正の整数でfactorial()を呼び出すと、数値を減算することで自分を再帰的に呼び出す.
再帰的手順を明確にするために、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      

数字が1に減少すると、再帰的に終了します.
再帰的なメリットとデメリット:
「プログラミングの美しさ」の観点から、偉大なコンピュータプログラミングの名言を引用します.
To iterate is human,to recurse divine. 反復者は人間、再帰者は神.–L. Peter Deutsch
メリット:

再帰的にコードをよりきれいに、優雅に見せる

は、複雑なタスクをより単純なサブ問題

に再帰的に分解することができる.

再帰的使用は、いくつかのネスト反復を使用するよりも容易である

欠点:

再帰論理はデバッグしにくく、

にフォローする.

再帰呼び出しは、メモリと時間が大量に消費されるため、コストが高い(効率が低い).

その他の参照

グラフィックアルゴリズム-再帰