Iteration count in recursive function

January 16, 2023

I am writing a recursive function to make permutations of digits from 0 to n. The program will return the th permutation that is obtained. It all works well but I had to use the cheap trick of defining count as a list, that is count=[0]. In this way I am using the properties of lists in order to properly update the variable count[0] at each iteration.

Ideally, what I would like to do is to define count as an integer number instead. However, this does not work because count is then updated only locally, within the scope of the function at the time it is called.

What is the proper way to count the iterations in a recursive function like this?

Below I show the code. It works, but I hate the way I am using count here.


import numpy as np

N=10
available=np.ones(N)

def permutations(array, count=[0], n=N, start=0, end=N, th=100):
    if count[0]<th:
        for i in range(n):
            if available[i]:                           
                array[start]=i
                if end-start>1:
                    available[i]=0
                    permutations(array, count, n, start+1, end)
                    available[i]=1
                else:
                    count[0]+=1
                    break
            if count[0]==th:
                a=''.join(str(i) for i in array)
                return a

def main():
    array=[0 for _ in range(N)]
    count=[0]
    print(permutations(array, count, N, start=0, end=N))

if __name__=="__main__":
    main()

>Solution :

Not necessarily ideal but to answer the question, one could use a global variable as follows:

import numpy as np

N = 10
available = np.ones(N)
count = 0


def permutations(array, n=N, start=0, end=N, th=100):
    global count
    if count < th:
        for i in range(n):
            if available[i]:
                array[start] = i
                if end-start > 1:
                    available[i] = 0
                    permutations(array, n, start+1, end)
                    available[i] = 1
                else:
                    count += 1
                    break
            if count == th:
                return ''.join(str(i) for i in array)



def main():
    array = [0 for _ in range(N)]
    print(permutations(array, N, start=0, end=N))
    print(f'{count=}')


if __name__ == "__main__":
    main()

Output: