Python: Calling multiple recursions simultaniously

Question

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?

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
– forivall, Commented Dec 18, 2012 at 20:25
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
– Óscar López, Commented Dec 18, 2012 at 21:12
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
– georg, Commented Dec 18, 2012 at 23:57

Rohit Jain · Accepted Answer · 2012-12-18 20:30:00Z

4

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

edited Dec 18, 2012 at 20:30

answered Dec 18, 2012 at 20:16

Rohit Jain

214k45 gold badges419 silver badges534 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Edward Loper · Accepted Answer · 2012-12-19 00:13:58Z

1

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.

edited Dec 19, 2012 at 0:13

answered Dec 18, 2012 at 20:19

Edward Loper

16k7 gold badges47 silver badges52 bronze badges

1 Comment

Rohit Jain Over a year ago

o.O. It will give an error even for integer value. Try n = 3.

Will C. · Accepted Answer · 2012-12-18 20:22:42Z

0

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)

answered Dec 18, 2012 at 20:22

Will C.

5993 silver badges8 bronze badges

Comments

Óscar López · Accepted Answer · 2012-12-18 21:11:38Z

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.

Collectives™ on Stack Overflow

Python: Calling multiple recursions simultaniously

4 Answers 4

Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related