Coding summation formula and recursive function

Question

Python beginner, running 2.7

I would like to define a function in Python, say N(d), recursively; with the following property: It sums the products a*b*N(a)N(b), for a and b integers greater than or equal to 0, and a + b = d, d is the variable. thanks.

Added

N(1)=N(2)=1

Okay. I would like you to define it too! We're on the same page :) — roippi, Nov 08 '13 at 07:09
@PeterVaro I don't know how to define functions recursively in python and I'm also having problems with the summation, I don't know the code for the summation over two indexes. — Jr., Nov 08 '13 at 07:15
I believe all recursive conditions should include a base condition and I dont see one here — thefourtheye, Nov 08 '13 at 07:15
@Jr. I'm sure you know how to define a non-recursive function, right? So you should write some code, and share that with us, okay? — Peter Varo, Nov 08 '13 at 07:17
possible duplicate of [How can I build a recursive function in python?](http://stackoverflow.com/questions/479343/how-can-i-build-a-recursive-function-in-python) — Peter Varo, Nov 08 '13 at 07:20

score 4 · Accepted Answer · edited Nov 08 '13 at 08:29

4

With memoization comes great performance in recursion.

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)

or, in a more concise way,

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]

edited Nov 08 '13 at 08:29

georg

211,518
52
313
390

answered Nov 08 '13 at 07:39

thefourtheye

233,700
52
457
497

I'd say this is _only_ possible with memoization. – georg Nov 08 '13 at 08:30
@thg435 You are right. I ran the accepted solution for 1000 an hour back and it hasnt returned yet. :( – thefourtheye Nov 08 '13 at 08:54
3

@thefourtheye: given that it gonna make roughly `195862343626786168428215594037354720883766227074392321135543758255826458866178503635670861311201194365023670769907049237918659938088980579535606329667844988744832625955306785759705892478365161670280059276679795265352436713425643620453565358970975803628223137500071162134155119169931688269254128630357946106789669416856086265219024651601168577321267615419985027793981221062495757027954891372595398605645786729791062435387274491014871947962543086223794720908470089299096719291852` recursive calls, you'll have to wait a bit ;) – georg Nov 08 '13 at 09:09
@thg435 How did you get N(1000)? i'm getting "maximum recursion depth exceeded", what does it mean? PS: The script works fine up to 900 – Jr. Nov 09 '13 at 02:40

score 1 · Answer 2 · answered Nov 08 '13 at 07:25

1

def N(d):
    if d == 1:
        return 1
    if d == 2:
        return 1
    sum = 0
    for i in range(1,d):
        tmp1 = N(i)
        tmp2 = N(d-i)
        sum += i*(d-i)*tmp1*tmp2
    return sum

print N(5)

answered Nov 08 '13 at 07:25

Naster

344
1
7

@Jr.Please check my memoized version also. – thefourtheye Nov 08 '13 at 07:41

Coding summation formula and recursive function

2 Answers2