python - 総和式と再帰関数のコーディング

Question

Python 初心者、2.7 を実行

Python で N(d) などの関数を再帰的に定義したいと思います。a および b の整数が 0 以上で、a + b = d、d が変数である場合に、積 a*b*N(a)N(b) を合計します。ありがとう。

追加した

N(1)=N(2)=1

Answer 1

メモ化により、再帰で優れたパフォーマンスが得られます。

def N(d, memoize = dict()):
    if d == 1 or d == 2: return 1
    if d in memoize: return memoize[d]
    result = 0
    for i in xrange(1, d):
        result += (d - i) * (i) * N(d - i) * N(i)
    memoize[d] = result
    return result

print N(1000)

または、より簡潔な方法で、

def N(d, memo={1:1, 2:1}):
    # http://oeis.org/A112915
    if d not in memo:
        memo[d] = sum(i * (d - i) * N(i) * N(d - i) for i in range(1, d))
    return memo[d]