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

Question

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?

Answer 1

>>> 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 Haskell¹ 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.

---

¹There 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.

Answer 2

It may be easier to understand if we take the recursion out of the picture. Here's a similar construct:

def funcA(lis, json, target):
    return json[target]

def funcB(lis, json, target):
    return funcA(lis[1:], json[lis[0]], target)

>>> final_json = funcB(my_list, my_json, 'ID')
>>> print(final_json)

Here, we can follow the execution path:

• We call funcB and pass it some arguments.
• funcB, in turn, calls funcA and passes that some arguments.
• funcA returns a value back to funcB.
• That value in turn is returned by funcB.
• The value funcB returns is assigned to final_json.

Now, your question is, why does it stop working if we redefine funcB as:

def funcB(lis, json, target):
    funcA(lis[1:], json[lis[0]], target)

With this redefinition, and everything else the same, the execution path is more like:

• We call funcB and pass it some arguments.
• funcB, in turn, calls funcA and passes that some arguments.
• funcA returns a value back to funcB.
• That value is ignored by funcB.
• funcB ends without returning a value, so by default it returns None.
• The value funcB returns is assigned to final_json.

Because funcB never explicitly returns the value it gets from funcA, it returns None by default.

---

Since a recursive function is simply a function that calls itself, its behavior is no different from a function that calls a different function.

Here is your function:

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

>>> final_json = funcB(my_list, my_json, 'ID')
>>> print(final_json)

Let's go through the same process as above, assuming it will recurse one time:

• We call recur and pass it some arguments.
• recur, in turn, calls recur again and passes some arguments.
• The second call to recur returns a value back to the first call.
• The first call to recur takes that value and returns it to us.
• The value the first call to recur returns is assigned to final_json.

If we remove the return, though:

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

• We call recur and pass it some arguments.
• recur, in turn, calls recur again and passes some arguments.
• The second call to recur returns a value back to the first call.
• The first call to recur takes that value and ignores it.
• The first call to recur ends without returning a value, so by default it returns None.
• The value the first call to recur returns is assigned to final_json.

Again, since the first call to recur never explicitly returns the result it gets from the second call to recur, it returns None by default.

---

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?

print is global, it writes to stdout without regard for function depth or stack frames. On the other hand, return exists on the function level, and only affects the value returned by a single function call. If that function call does nothing with the return value of the function it calls, that value is lost.

---

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.

Haskell functions define exactly one value; there's no need for an explicit return because the entire body of the function is in an implicit one. Other languages, such as the Lisp family, always return the value of the last line in the block, so an explicit return in this case is also unnecessary.

Note that in both of these cases, both of your return statements would be missing, not just the second one; this is about returns in general, and has nothing to do with recursive calls.

Python, and most other mainstream languages, require an explicit return, if you want to return any useful value.

Answer 3

Best way I can think of to demonstrate this is to compare a very simple recursive recursive function, in a few different languages. The function I've chosen will compute the factorial of an integer. (A non-negative one, and for simplicity I won't attempt to perform any validation to stop the function blowing up if presented with a negative integer, or a float, or something stupid.)

Firstly, in Python:

def factorial(n):
    if (n == 0):
        return 1
    return n * factorial(n-1)

So here you have the "intermediate value returned", which seems to be what you're claiming seems to be unique to Python. (Of course you're not returning the result of the recursive call itself, but a simple operation performed on it - but that doesn't change the situation, unless I've totally misunderstood. You're still returning the value, in order to do something with this "intermediate result".)

So lets have a look at how you would do the same in Javascript. (Yes, there are more elegant ways to do this, in both languages, but I'm trying to keep things simple and strictly comparable.)

function factorial(n) {
    if (n == 0) {
       return 1;
    }
    return n * factorial(n-1);
}

I hope you'll agree that, putting aside trivial differences in basic syntax, the JS version is identical to the Python one above. In particular, both do that "return the intermediate value" thing.

I could write exactly the same thing in PHP, or (although I'm not so familiar with those languages) I think in C/C++/C#/Java, and it would again be very much the same.

Now if we finally come to Haskell, which is really a radically different type of language from all the above, let's look at how one might define the same function:

factorial :: Integer -> Integer
factorial n
    | n==0 = 1
    | otherwise = n * factorial (n-1)

Yes, there's no explicit return statement here. But that's only because Haskell functions are "pure" functions that must always result in a value, so instead of having an explicit statement to tell you what that value would be, at the end of some more complex code, you just define what its result is on each possible input.

Of course, you can and often do define functions more abstractly, in "point free" style using composition and other higher-order operations - this is one of the benefits of functional programming. But at the end of the day, in Haskell a function is ultimately defined in terms of what output it results in for a given input - this is actually fundamental, it's what the word "function" means in mathematics, and what it also means in purely functional languages. (As opposed to a mere "procedure", a reusable block of code that may or may not result in a value, as in most procedural languages like JS, Python and the rest.)

So in other words, the above still "returns the intermediate value". The = sign in the final line of the example does the work of the return statement in other languages.

So I apologise if I've gone on for too long about a really simple topic - I'm just still quite unsure as to where your confusion lies. But I hope this has helped you overcome it.

Answer 4

This isn't specific to Python; it's specific to all C-like and C-adjacent languages (perhaps all imperative languages), and, weighted by popularity, Haskell is the odd one out. In C, C++, Python, Perl, PHP, etc., a statement of the form return expression returns the given expression from the function, while just expression evaluates the expression and throws it away without returning it. It's only in more functional languages like Haskell and Scheme, where a function definition tends to only have one statement, that the "return" is implicit.