Pythonで再帰的な関数を作るにはどうしたらいいですか？

Pythonで再帰的な関数を作るにはどうしたらいいですか？

Robert Gowland
編集された質問 25日 9月 2012 в 5:45
プログラミング
recursion python
26日 1月 2009 в 10:24
10 ビュー
質問へのコメント (1)

再帰的という意味でしょうか？以下は、階乗関数を計算する再帰的な関数の簡単な例です。

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

再帰的アルゴリズムの重要な要素は次の2つです。

  • 終了条件： n == 0
  • 関数が毎回小さな数で自分自身を呼び出す削減ステップ： factorial(n - 1).
解説 (6)

Pythonでの再帰は、他の言語での再帰と同じように機能し、再帰的な構成はそれ自体で定義されます。

たとえば、再帰クラスはバイナリツリー(または任意のツリー)です。

class tree():
    def __init__(self):
        '''Initialise the tree'''
        self.Data = None
        self.Count = 0
        self.LeftSubtree = None
        self.RightSubtree = None

    def Insert(self, data):
        '''Add an item of data to the tree'''
        if self.Data == None:
            self.Data = data
            self.Count += 1
        elif data < self.Data:
            if self.LeftSubtree == None:
                # tree is a recurive class definition
                self.LeftSubtree = tree()
            # Insert is a recursive function
            self.LeftSubtree.Insert(data)
        elif data == self.Data:
            self.Count += 1
        elif data > self.Data:
            if self.RightSubtree == None:
                self.RightSubtree = tree()
            self.RightSubtree.Insert(data)

if __name__ == '__main__':
    T = tree()
    # The root node
    T.Insert('b')
    # Will be put into the left subtree
    T.Insert('a')
    # Will be put into the right subtree
    T.Insert('c')

すでに述べたように、再帰構造には終了条件が必要です。 このクラスでは、新しい要素が追加された場合にのみ再帰し、1回だけ追加されるため、それほど明白ではありません。

また、注目に値するのは、デフォルトではpythonには、コンピューターのすべてのメモリを吸収しないようにするために、利用可能な再帰の深さに制限があることです。 私のコンピュータでは、これは1000です。 これがハードウェアなどによって変わるかどうかはわかりません。 あなたのものを見るために:

import sys
sys.getrecursionlimit()

そしてそれを設定するには:

import sys #(if you haven't already)
sys.setrecursionlimit()

編集:私のバイナリツリーがこれまでで最も効率的なデザインであることを保証することはできません。 誰かがそれを改善できるなら、私はその方法を聞いて幸せです。

解説 (0)

例えば、次のように構築するとしよう。 u(n+1)=f(u(n)) で、u(0)=u0 とします。

一つの解決策は、簡単な再帰的関数を定義することである。

u0 = ...

def f(x):
  ...

def u(n):
  if n==0: return u0
  return f(u(n-1))

残念ながら、uの高い値を計算したい場合は、スタックオーバーフローエラーに遭遇します。

もう一つの解決策は、単純なループです。

def u(n):
  ux = u0
  for i in xrange(n):
    ux=f(ux)
  return ux

しかし、異なるnの値に対して複数のuの値が必要な場合、これは最適とは言えません。 すべての値を配列にキャッシュすることもできますが、メモリ不足のエラーに遭遇する可能性があります。 代わりにジェネレータを使うとよいでしょう。

def u(n):
  ux = u0
  for i in xrange(n):
    ux=f(ux)
  yield ux

for val in u(1000):
  print val

他にもいろいろな方法がありますが、主なものはこれだけでしょう。

解説 (2)

再帰的関数の例。

def recursive(string, num):
    print "#%s - %s" % (string, num)
    recursive(string, num+1)

で実行します。

recursive("Hello world", 0)
James
編集した答え 11日 3月 2014 в 9:07
解説 (4)