CODEWITHSUNDEEP
pythonpython-3.x
tastyminerals
tastyminerals

Reputation: 6538

Why does a recursive function returns this value?

I am trying to understand why does the recursive function returns 1003 instead of 1005.

l = [1,2,3]
def sum(l):
    x, *y = l
    return x + sum(y) if y else 1000

sum(l)

According to pythontutor the last value of y list is 5 and that would make return value 1000 + sum([2,3]) 1005, am I correct?

enter image description here

Upvotes: 0

Views: 143

Answers (4)

freakish
freakish

Reputation: 56467

Recursion step by step

1) x = 1 y = [2,3]

2) x = 2 y = [3]

3) x = 3 y = []

Note that step 3) returns 1000 since not y. This is because your return statement is equivalent to 

(x + sum(y)) if y else 1000

Thus we have

3) 1000

2) 1000 + 2

1) 1002 + 1

The result is 1003.

So perhaps what you are looking for is:

return x + sum(y) if y else 1000 + x

or (copied from ndpu's answer):

return x + (sum(y) if y else 1000)

(take x into account in last step)

Upvotes: 2

ndpu
ndpu

Reputation: 22561

You should add parentheses:

l = [1,2,3]
def sum(l):
    x, *y = l
    return x + (sum(y) if y else 1000)

Upvotes: 2

Loïc Faure-Lacroix
Loïc Faure-Lacroix

Reputation: 13600

You should try to use a debugger or actually print things inside the function. Without executing the code I guess that it should be something like this:

l = [1,2,3]
def sum(l):
    x, *y = l
    return x + sum(y) if y else 1000

sum(l)

It will call a such:

-> sum([1,2,3])
x : 1
y : [2, 3]
-> sum([2, 3])
x: 2
y: [3]
-> sum([3])
x: 3
y: []
returns 1000
returns 2 + 1000
returns 1 + 1002

Upvotes: 1

abarnert
abarnert

Reputation: 365667

According to pythontutor the last value of y list is 5 and that would make return value 1000 + sum([2,3]) 1005, am I correct?

No, the last value of y is []. It's never anything but a list, and besides, there are no 5s for it to ever be. On top of that, the recursive return value is always on the right of the +, only the x is ever on the left.

Let's step through it:

sum([1, 2, 3]) = 1 + sum([2, 3])
sum([2, 3]) = 2 + sum([3])
sum([3]) = 1000

So, substituting back:

sum([2, 3]) = 2 + 1000 = 1002
sum([1, 2, 3] = 1 + 1002 = 1003

The problem is that when y is empty, you're returning 1000, not x + 1000.

Your confusion may just be a matter of precedence. Maybe you expected this:

return x + sum(y) if y else 1000

… to mean this:

return x + (sum(y) if y else 1000)

… but actually, it means this:

return (x + sum(y)) if y else 1000

Upvotes: 3

Related Questions