Recursive function not returning anything, even though it seems like it was going to

Question

I am trying to do this problem:

https://leetcode.com/problems/maximum-swap/description/

My method is basically "Check if the first digit in your number is the largest digit. If it is not, then swap it with the largest digit. If it is, then set aside the first digit in a list (called beginning), then do the same procedure on the new number (the one with the first digit chopped off)."

To do this I wrote a recursive function called swapper which I call elsewhere. I feed into it a list of the digits. It works correctly if

def swapper(digits, beginning):
    print 'running: digits, beginning: ', digits, beginning
    if len(digits) > 0: #If there is anything left in the number, continue checking if the first digit is the largest)
        if digits.index(max(digits)) == 0:
            beginning.append(digits[0])
            print 'iterating: digits, beginning = ', digits[1:], beginning
            swapper(digits[1:], beginning) #recursively run the function with a smaller digit list
        else:
            digits[digits.index(max(digits))], digits[0] = digits[0], 
max(digits)
            return beginning + digits
    else: #If there is nothing left in the number, return the beginning list
          #which is just all the digits at this point
        print 'returning beginning'
        print 'beginning: ', beginning
        return beginning

#pseudocode here: digits = digits(digits of the number) 
results = swapper(digits, [])
print 'results: ', results

It works if it never hits that commented "else" inside swapper, but if it does, it doesn't seem to return anything. Using the example number 9973, the stdout is:

running: digits, beginning:  [9, 9, 7, 3] []
iterating: digits, beginning =  [9, 7, 3] [9]
running: digits, beginning:  [9, 7, 3] [9]
iterating: digits, beginning =  [7, 3] [9, 9]
running: digits, beginning:  [7, 3] [9, 9]
iterating: digits, beginning =  [3] [9, 9, 7]
running: digits, beginning:  [3] [9, 9, 7]
iterating: digits, beginning =  [] [9, 9, 7, 3]
running: digits, beginning:  [] [9, 9, 7, 3]
returning beginning
beginning:  [9, 9, 7, 3]
results:  None

It looks like it correctly partitions the digits into the beginning list. It then properly prints "beginning: ", beginning. The list exists and it's [9,9,7,3] like I expect. It's then supposed to return that. But when I print results outside the function it's just None. Why?

It returns properly via the other return statement (the one that says "return beginning + digits").

Your problem isn't exactly the same as in the linked question, but the core issue is the same: you're discarding the result from the recursive call. — PM 2Ring, Sep 19 '18 at 21:29
@PM2Ring Thank you, I failed to find that thread when looking somehow. Closing here — iammax, Sep 19 '18 at 21:30
No worries. There's no harm in asking a duplicate question (as long as you make some effort to check for dupes first). It's just the duplicate answers that can be a problem, since we want them all to be in one place so people can find them and compare them easily, and so they can be properly sorted by the voting process. And in this case, since your problem's slightly different it's fine that it has an answer explaining the difference. — PM 2Ring, Sep 19 '18 at 21:34

Henry Woody · Accepted Answer · 2018-09-19T22:28:37.530

While your function works properly when building up a solution and going deeper into recursion, the problem is when you start to work your way back out after reaching the base case. So far your code will not pass the results of the recursive calls back up to the call above.

You need to return the results of the recursive call. Putting return in front of the recursive call swapper(digits[1:], beginning) will do that in your case.

Here's what it'll all look like:

def swapper(digits, beginning):
    print 'running: digits, beginning: ', digits, beginning
    if len(digits) > 0: #If there is anything left in the number, continue checking if the first digit is the largest)
        if digits.index(max(digits)) == 0:
            beginning.append(digits[0])
            print 'iterating: digits, beginning = ', digits[1:], beginning
            # ADDED: return
            return swapper(digits[1:], beginning) #recursively run the function with a smaller digit list
        else:
            digits[digits.index(max(digits))], digits[0] = digits[0], max(digits)
            return beginning + digits
    else: #If there is nothing left in the number, return the beginning list
          #which is just all the digits at this point
        print 'returning beginning'
        print 'beginning: ', beginning
        return beginning

#pseudocode here: digits = digits(digits of the number) 
results = swapper([9, 9, 7, 3],[])
print('results: ', results)

With the output:

running: digits, beginning:  [9, 9, 7, 3] []
iterating: digits, beginning =  [9, 7, 3] [9]
running: digits, beginning:  [9, 7, 3] [9]
iterating: digits, beginning =  [7, 3] [9, 9]
running: digits, beginning:  [7, 3] [9, 9]
iterating: digits, beginning =  [3] [9, 9, 7]
running: digits, beginning:  [3] [9, 9, 7]
iterating: digits, beginning =  [] [9, 9, 7, 3]
running: digits, beginning:  [] [9, 9, 7, 3]
returning beginning
beginning:  [9, 9, 7, 3]
results: [9, 9, 7, 3]

You could put a repaired version of the OP's code in your answer and show that it does the right thing... ;) — PM 2Ring, Sep 19 '18 at 21:30

Recursive function not returning anything, even though it seems like it was going to

1 Answers1