再帰を使用してこの数式をコード化することは可能ですか？

Question

再帰を使用して次の数式をコード化しようとしています。 私はさまざまな方法でそれをやろうと考えていましたが、式が再帰的であるため、再帰が必要です。 私は単純な問題に再帰を適用する方法を知っていますが、この特定のケースでは私の理解は間違っているようです。私はpythonでそれをコーディングしようとしましたが、コードはメッセージ

RuntimeError: maximum recursion depth exceeded 

で失敗したので、私はこの表現と再帰は全く可能であるかどうかをコーディングするための最良の方法は何かお願いしたいと思います。

私が試したPythonコードである：

def coeff(l,m,m0,m1): 
    if l==0 and m==0: 
    return 1. 
    elif l==1 and m==0: 
    return -(m1+m0)/(m1-m0) 
    elif l==1 and m==1 : 
    return 1./(m1-m0) 
    elif m<0 or m>l: 
    return 0. 
    else: 
    return -((l+1.)*(m1-m0))/((2.*l+1.)*(m1+m0))* \ 
    ((2.*l+1.)*(m+1.)/((l+1.)*(2.*m+3.)*(m1-m0))*coeff(l,m+1,m0,m1) +\ 
     (2.*l+1.)*m/((l+1.)*(2.*m-1.)*(m1-m0))*coeff(l,m-1,m0,m1) -\ 
     l/(l+1.)*coeff(l-1,m,m0,m1)) 

x=m1-m0とy=m1+m0。私のコードでは、他の関数としての係数をa(l,m)で表現しようとし、それに基づいて再帰をコーディングしました。

Answer 1

ここで素朴な再帰的実装は、明らかに同じことを何度も何度も再計算します。おそらく以前に計算されたものを保存することに払うでしょう。これは、明示的に表を記入するか、暗黙的にメモを取ることによって行うことができます（したがって、「再帰と動的プログラミング」に関するコメントには本当に同意しません）。 this decoratorを使用して

例えば、

class memoize(dict): 
    def __init__(self, func): 
     self.func = func 

    def __call__(self, *args): 
     return self[args] 

    def __missing__(self, key): 
     result = self[key] = self.func(*key) 
     return result 

あなたが同じリンクが呼び出し間でキャッシュしたバージョンが含まれていることを

@memoize 
def calc_a(l, m, x, y): 
    if l == 0 and m == 0: 
     return 1 
    # Rest of formula goes here. 

注意として、それを書くことができます。

（メモ化）再帰と明示的なテーブルの建物の間のトレードオフの数があります。

1. 再帰は、またはあなたのケースでは問題ではないかもしれない可能性があります（通常の呼び出しの数がより限られています - 元のコードには無限の再帰問題があるようです）。

2. メモ化された再帰は、明示的なループを使用した明示的な表の構築よりも実装が簡単です（おそらく）。