Recursion equation does not seem to execute properly in Python

Question

I have the following Python equation:

def E(r, b):
    if r == 0:
        return 0
    elif b == 0:
        return r
    else:
        return max(0, (r/(r+b))*[1+E(r-1,b)]+(b/(r+b))*[E(r,b-1)-1])

print E(1,1)

The recursion does not seem to work. For E(1, 1) the mathematical equation should return 1/2. However I am getting 0. And for E(2, 2), I am getting an error, when mathematically it should be 2/3.

from __future__ import division
def E(r, b):
    if r == 0:
        return 0
    elif b == 0:
        return r
    else:
        return max(0, (float(r)/float(r+b))*[1+E(r-1,b)]+(float(b)/float(r+b))*[E(r,b-1)-1])

print E(1,1)

I made the following adjustments but still ran into errors: "TypeError: can't multiply sequence by non-int of type 'float'"

score 3 · Accepted Answer · edited May 23 '17 at 10:10

3

For Python 2, When you substitute r = 1 and b = 1, the front part of the equation becomes:

1 / (1+1) = 0

So the max will always return max(0, 0)

@Alik mentions from __future__ import division if you need floating point division

>>> from __future__ import division
>>> def E(r, b):
...     if r == 0:
...         return 0
...     elif b == 0:
...         return r
...     else:
...         return max(0, (r/(r+b))*(1+E(r-1,b))+(b/(r+b))*(E(r,b-1)-1))
...
>>> print (E(1,1))
0.5
>>> print (E(2,2))
0.666666666667
>>>

edited May 23 '17 at 10:10

Community

1
1

answered Apr 19 '15 at 04:10

dting

38,604
10
95
114

Shouldn't the first part be 1/2? – AG10 Apr 19 '15 at 04:11
What version of python are you using? If it is python2, division will return an int. – dting Apr 19 '15 at 04:12
Force the variables to floats to get floating point division. – jwilner Apr 19 '15 at 04:13
I am running Python2. – AG10 Apr 19 '15 at 04:13
2

@VMO take a look at this question http://stackoverflow.com/questions/1267869/how-can-i-force-division-to-be-floating-point-in-python – Konstantin Apr 19 '15 at 04:13
I made the adjustments but am still receiving a type error: "TypeError: can't multiply sequence by non-int of type 'float'" – AG10 Apr 19 '15 at 04:20
You cant multiply a list with a float, don't use square braces for order of operations. – dting Apr 19 '15 at 04:20
@DTing I understand now. Thank you Alik and DTing for clarifying. I appreciate it. – AG10 Apr 19 '15 at 04:26

score 1 · Answer 2 · answered Apr 19 '15 at 04:44

The problem is as best as I can tell that you are using ints where you want to use floats, also I'm guessing that you are using the square brackets as an alternative to using two parenthesis in a row. Python is interpreting the square brackets as a list and when you multiply a list by an int python will return a list with that many repetitions of the list

 ['a', 'b'] * 5
 ['a', 'b', 'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b']

When you tried to multiply the list by a float python can't handle it and just returns a type error. It looks like if you just change the ints to floats and replace the square brackets with parens you should be good.

def E(r, b):
    r = float(r)
    b = float(b)
    if r == 0:
        return 0
    elif b == 0:
       return r
    else:
        return max(0, (r/(r+b))*(1+E(r-1,b))+(b/(r+b))*(E(r,b-1)-1))

print E(1,1)

Recursion equation does not seem to execute properly in Python

2 Answers2