Python: Calling multiple recursions simultaniously

1
votes

I'm getting this error:

TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

For this code:

def a(n):
    if n < 0:
        return 0
    if n == 1:
        return 1
    if n > 1:
        return a(n-1) + a(n-2) + a(n-3)

How should I call multiple recursions?

4
pythonrecursion
When doing recursion, make sure that your functions always return something. In your case, you have some cases that are missed in your if statements, so the quick fix is to add something like return 0 at the end of your function. – forivall
Something tells me that you're missing one case. What happens if n == 2? there should be yet another case for handling this. – Óscar López
As a side note, this is a remarkably inefficient way to generate Tribonacci numbers. The simple a, b, c = b, c, a + b + c will work far better. – georg

4 Answers

4
votes

You are missing the condition: - 1 > n >= 0. And thus, you are not returning any value in case your n >= 0 and n < 1.

May be your first condition is supposed to be: -

if n < 1:
    return 0
1
votes

To elaborate on Rohit's answer: if a python function gets to the end without returning anything, then it implicitly returns None. So a(0.5) will return None. If you call eg a(1.5), then you'll end up with a(0.5)+a(-0.5)+a(-1.5) which evaluates to None+0+0 which gives you the error you describe.

0
votes

The problem is when n = 0, there is no if statement to handle this, so the python function implicitly return a NoneType object, change it to this:

def a(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n > 1:
        return a(n-1) + a(n-2) + a(n-3)
0
votes

Try this:

def a(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return a(n-1) + a(n-2) + a(n-3)

The trick is, that you have to cover all the possible values. You weren't covering n == 0, and the last condition should be an else, so it's explicit that there can be no other choices.

Notice that the error unsupported operand type(s) for +: 'int' and 'NoneType' happened before because if none of the conditions was met (for example, when n == 0) then None was returned, and at some point in the recursion an int was added to None, causing the error. This is why it's important to be very exhaustive when covering all possibilities in a recursion, making sure that all possible cases are being considered.

And by the way: something tells me that you're missing one case. What happens if n == 2? there should be yet another case for handling this.