in reply to recursive formula.

What should the result be for P( 1, 1, 1 )?

My interpretation is that each term will be: P( 1 - 1 )P( ... )

Which as 1 - 1 will always be zero, the results of the multiplication is zero, so the overall results will be zero?

If this is the case, then herveus' solution is incorrect as given input of ( 1, 1, 1 ), he returns 1.

If I'm correct, of which there is no guarentee, then I think that the problem lies with his simple expedient of prefixing the list with a 0 to get around the "indices starting from 1" problem, which is causing the function to iterate and recurse once too often.

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

Replies are listed 'Best First'.
Re^2: recursive formula.
by rsteinke (Scribe) on Aug 07, 2004 at 01:00 UTC
    You forget that r_0 is always zero, so 
    P(1, 1, 1) = (1 - 1) P(1, 1) + (1 - 1) P(1, 1) + (1 - 0) P(1, 1)
           = P(1, 1) = P(1) = 1

    [download]
    Ron Steinke rsteinke@w-link.net
[reply]
[d/l]

      Thanks. That's the source of my misunderstanding. I saw the r0 = 0 reference, but I also saw r running 1 .. n and i running 1 to n.

      I missed that n-i = 0 whenever n=i. Stupid.

      Examine what is said, not who speaks.
      "Efficiency is intelligent laziness." -David Dunham
      "Think for yourself!" - Abigail
      "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
[reply]

In Section Seekers of Perl Wisdom