Python recursion returns none, not sure whats going on here

Question

having trouble here, trying to get the counter as return, but getting none instead. I'm pretty sure this is some silly mistake on my part, but after 2hours of looking and googling, I've decided to reach out, thanks.

def minimumSwaps(arr):
    def swapper(counter, arr2):
        out_of_place = []
        for i in range(len(arr2)):
            if arr2[i] is not i + 1:
                out_of_place.append([abs(arr2[i] - (i + 1)), arr2[i], i])

        if len(out_of_place) == 0:
            print(counter, arr2)
            return counter

        out_of_place = sorted(out_of_place, reverse=True)
        max1 = out_of_place[0]
        max2 = out_of_place[1]

        arr2[max1[2]] = max2[1]
        arr2[max2[2]] = max1[1]
        counter += 1

        swapper(counter, arr2)

    return swapper(0, arr)


print(minimumSwaps([1, 3, 5, 2, 4, 6, 7]))

change swapper(counter, arr2) to return swapper(counter, arr2) — Robin, May 15 '21 at 23:25

score 0 · Answer 1 · answered May 15 '21 at 23:25

0

Your inner function is missing a return value

def minimumSwaps(arr):
    def swapper(counter, arr2):
        out_of_place = []
        for i in range(len(arr2)):
            if arr2[i] is not i + 1:
                out_of_place.append([abs(arr2[i] - (i + 1)), arr2[i], i])

        if len(out_of_place) == 0:
            print(counter, arr2)
            return counter

        out_of_place = sorted(out_of_place, reverse=True)
        max1 = out_of_place[0]
        max2 = out_of_place[1]

        arr2[max1[2]] = max2[1]
        arr2[max2[2]] = max1[1]
        counter += 1

        return swapper(counter, arr2)
    return swapper(0, arr)


print(minimumSwaps([1, 3, 5, 2, 4, 6, 7])) # prints 3

answered May 15 '21 at 23:25

spo

304
1
7

1

Could you explain further please? I thought the 'return counter' was sufficient. – Jorge May 15 '21 at 23:29
The last stack on your recursion will return the 'counter' because that's where len(out_of_place) == 0. On every other stack, the code gets to `swapper(counter, arr2)` and if you don't return that, python by default returns None. So every other stack thats not the last one is returning None up the chain. – spo May 16 '21 at 02:06

Anandu Sreekumar · Answer 2 · 2021-05-16T09:11:19.180

In recursion you have to return the current data (nth call) to the previous call(n-1 th call), otherwise it would return 'None' to the previous call and so on. Here, I have added return to swapper() function:

def minimumSwaps(arr):
    def swapper(counter, arr2):
        out_of_place = []
        for i in range(len(arr2)):
            if arr2[i] is not i + 1:
                out_of_place.append([abs(arr2[i] - (i + 1)), arr2[i], i])

        if len(out_of_place) == 0:
            print(counter, arr2)
            return counter

        out_of_place = sorted(out_of_place, reverse=True)
        max1 = out_of_place[0]
        max2 = out_of_place[1]

        arr2[max1[2]] = max2[1]
        arr2[max2[2]] = max1[1]
        counter += 1

        return swapper(counter, arr2)

    return swapper(0, arr)


print(minimumSwaps([1, 3, 5, 2, 4, 6, 7]))

This returned desired output as 3

@Jorge : Your nth call should return data to n-1 th call. – Anandu Sreekumar May 15 '21 at 23:38 — Anandu Sreekumar, May 15 '21 at 23:38

Python recursion returns none, not sure whats going on here

2 Answers2