Recursion won't stop executing after an if-statement

Question

I have this code

def swap(a, i, j):
    a[i], a[j] = a[j], a[i]


def permute(a, i, n):
    if (a == b):
        print('String matched')
    else:
        if i == n:
            print(a)
        for j in range(i, n + 1):
            swap(a, i, j)
            permute(a, i + 1, n)
            swap(a, i, j)


def main():

    string = "ABCD"
    n = len(string)
    a = list(string)
    global b
    b = list("ABDC")
    permute(a, 0, n - 1)


if __name__ == '__main__':
    main()

My goal is to stop the loop when string a matched string b, but the program output is

['A', 'B', 'C', 'D']
String matched
['A', 'C', 'B', 'D']
['A', 'C', 'D', 'B']
['A', 'D', 'C', 'B']
['A', 'D', 'B', 'C']
['B', 'A', 'C', 'D']
['B', 'A', 'D', 'C']
['B', 'C', 'A', 'D']
['B', 'C', 'D', 'A']
['B', 'D', 'C', 'A']
['B', 'D', 'A', 'C']
['C', 'B', 'A', 'D']
['C', 'B', 'D', 'A']
['C', 'A', 'B', 'D']
['C', 'A', 'D', 'B']
['C', 'D', 'A', 'B']
['C', 'D', 'B', 'A']
['D', 'B', 'C', 'A']
['D', 'B', 'A', 'C']
['D', 'C', 'B', 'A']
['D', 'C', 'A', 'B']
['D', 'A', 'C', 'B']
['D', 'A', 'B', 'C']

Process finished with exit code 0

as we can see, the "String matched" is replacing the matched string (which means the if-condition is working). My problem is, the loop still works after that.

Next try: putting return false for the if-statement. The output is still the same unfortunately

Does anyone knows how to stop the looping?

Answer 1

You can add additional variables.

For example:

def swap(a, i, j):
    a[i], a[j] = a[j], a[i]


def permute(a, i, n):
    if (a == b):
        global flag
        flag = True
        print('String matched')
    elif not flag:
        if i == n:
            print(a)
        for j in range(i, n + 1):
            swap(a, i, j)
            permute(a, i + 1, n)
            swap(a, i, j)


def main():

    string = "ABCD"
    n = len(string)
    a = list(string)
    global flag
    global b
    flag = False
    b = list("ABDC")
    permute(a, 0, n - 1)


if __name__ == '__main__':
    main()