Convert recursion to iteration when there are loops in the function

Question

I am converting some of the recursive calls in our code base to iterations. This has been pretty straightforward, thanks to this blog, and this question. However, there is the following pattern (as a minimal example), which is giving me a hard time. It basically gives n^m permutations (with repetition) of n numbers in m positions (here n=4, m=3):

def f (i, arr):
    if i < len(arr):
        for j in [2,3,5,8]:
            arr[i] = j
            f(i+1, arr)
    else:
        print(arr)

f(0, [0,0,0])

which outputs:

[2, 2, 2]
[2, 2, 3]
[2, 2, 5]
...
[8, 8, 3]
[8, 8, 5]
[8, 8, 8]

According to this discussion, this should be possible. It would be great if someone can share some guidance as to how to proceed with this conversion?

Can you modify the function to *not* use a loop, but just recursion? That would be simpler to convert. — Scott Hunter, Sep 16 '20 at 18:00

score 2 · Accepted Answer · edited Sep 16 '20 at 19:11

It might be helpful to take a step back from the code and to instead think about what pattern you're trying to generate here. Imagine, for example, that you had ten options of numbers to pick from per slot, and they were 0, 1, 2, ..., 9. In that case, what you're doing is essentially counting upward starting at 000 until you eventually reach 999. And how do you do that? Well:

If the last digit is not 9, add one to it. You're done.
Otherwise, the digit is a 9. Roll it back over to 0, then move to the preceding digit.

In your case, it's the numbers 2, 3, 5, and 8, but that doesn't really matter.

You can translate that into a nice procedure for a more general problem of listing all ways of writing out n symbols taken from a list of k options:

def list_all_options(length, options):
    # Initially, pick the first option in each slot. This array stores
    # indices rather than values.
    curr = [0] * length
    
    while True:
        # Print what we have, mapping from indices to values.
        print([options[index] for index in curr])
        
        # Roll over all copies of the last digit from the end, backing
        # up as we go.
        pos = len(curr) - 1
        while pos >= 0 and curr[pos] == len(options) - 1:
            curr[pos] = 0
            pos -= 1
        
        # If we rolled all digits, we're done!
        if pos == -1: break
        
        # Otherwise, increment this digit.
        curr[pos] += 1

Thanks a lot, great way of thinking about the problem. – a.sam Sep 16 '20 at 18:28 — a.sam, Sep 16 '20 at 18:28

Convert recursion to iteration when there are loops in the function

1 Answers1