Is returning the intermediate value in a recursive function a quirk of python?

  • A+
Category:Languages

UPDATE: Let me clarify what exactly is so confusing about this. If I add a print statement like such:

    def recur(lis, json, target):         if lis[0] == target:             print(json[tagert])             return json[target]         else:             recur(lis[1:], json[lis[0]], target) 

my print statement will display the expected value of the JSON. I don't know how else to phrase this. Given that the line preceding the return statement gives the result I expect (without the return statement in the else) why is the return statement in the else necessary?

And for those of you that insist on downvoting this, I've looked at the multiple times the question about a missing return statement was asked. What's never been answered in any of those is WHY the return is necessary. Downvote me all you want but at least understand that you're downvoting a good question. I thought this community was maturing but obviously not.


So I've looked at several questions with the same title as mine and I still don't quite understand why this is the case.

If I have a recursive function like this:

def recur(lis, json, target):     if lis[0] == target:         return json[target]     else:         return recur(lis[1:], json[lis[0]], target) 

I get my return value as expected.

But if I don't return the in the else statement, I get a None:

def recur(lis, json, target):     if lis[0] == target:         return json[target]     else:         recur(lis[1:], json[lis[0]], target) 
>>> final_json = recur(my_list, my_json, 'ID') >>> print(final_json)    None 

Is this specific to Python? I'm a bit rusty but I seem to remember languages like Haskell handling this more elegantly where, I believe, I don't need to return the value of the recursive call. Which makes more sense to me - I don't need all the intermediate values since I'm passing my function all the values it needs at each level of the stack. What am I missing here?

 


>>> final_json = recur(my_list, my_json, 'ID') >>> print(final_json)    None 

if I don't return the in the else statement, I get a None … I don't need all the intermediate values since I'm passing my function all the values it needs at each level of the stack. What am I missing here?

In your function call final_json = recur(...) you are stating that final_json is whatever recur returns.

If this is your implementation:

def recur(lis, json, target):                # line 1     if lis[0] == target:                     # line 2         print(json[tagert])                  # line 3         return json[target]                  # line 4     else:                                    # line 5         recur(lis[1:], json[lis[0]], target) # line 6  recur(myArg1, myArg2, myArg3)                # line 7 

Then consider exactly what happens if you call recur(someLis, someJson, someTarget) where lis[0] does NOT equal target.

In a pseudo-stack-trace:

RECUR CALL A ├─ A condition fails (line #2) ├─ A calls `recur` (l#6) │    └─ RECUR CALL B │       ├─ B condition fails (#2) │       ├─ B calls `recur` (#6) │       │    └─ RECUR CALL C │       │       ├─ C condition passes (#2) │       │       ├─ C prints answer (#3) │       │       └─ C returns answer to B (#4) │       ├─ B receives answer from C (#6) │       └─ B returns `None` (because you didn't use `return`) (#6) ├─ A receives `None` from B (#6) └─ A returns `None` (because you didn't use `return`) (#6) 

Unless your outermost recur call happens to be on a base case (passing the condition if lis[0]...), the relevant line is line 6, where you have no return keyword.

Yes, you calculated the eventual answer on lines 3 & 4.

Yes, you return the answer on line 4.

But that return is for the call on line 6! Not the top-level call (line 7).

So you end up back at line 6, having calculated the answer you wanted and… you do nothing with it. You don't return it. It goes nowhere.

Eventually the stack unwinds to the top level call (line 7), which receives the default Python return value (None), which was the result of the last line of the function that ran (line 6), because that line had no return statement.

The issue isn't that Haskell "doesn't need to return the intermediate calls." It's actually the exact opposite; Haskell automatically returns its function bodies. There is no explicit return keyword in Haskell1 because you are ALWAYS returning something implicitly, you just don't need to remember to type it yourself.

Here is an equivalent example:

def ret5 ():     return 5  def example ():     return ret5()  def final ():     example() 

If you call result = final(), then result will clearly be None, right? It doesn't matter that final called example, which returned the answer you wanted. Since final didn't return the result of example, the top-level output is still None, even though you did "reach" the answer at some point during program execution.


1There is unfortunately a function in Haskell named return which has nothing to do with returning values from functions. It's a lamentable name choice which was presumably selected to make do-notation look more imperative. I prefer the identical function pure for this reason.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: