How to rewrite a recursive function to use a loop instead?

Question

This stack overflow thread claims that every recursive function can be written as a loop.

Which recursive functions cannot be rewritten using loops?

It makes complete sense. But I'm not sure how to express the following recursive function as a loop because it has a pre recursive piece of logic and a post recursive piece of logic.

Obviously the solution cannot use the goto statement. The code is here:

def gen_perms(lst, k, m):

    if k == m:
        all_perms.append(list(lst))
    else:
        for i in xrange(k, m+1):

            #swap char
            tmp = lst[k]
            lst[k] = lst[i]
            lst[i] = tmp

            gen_perms(lst, k+1, m)

            #swap char
            tmp = lst[k]
            lst[k] = lst[i]
            lst[i] = tmp

Invoking it would be like this:

all_perms = []
gen_perm([1, 2, 3], 0, 2)

and it generates every permutation of the list 1,2,3.

Personally....I think it can be solved but you need quote a few variables to manage the fact your recursion is performed inside a loop...thus you need to store the loop position and the direction you're travelling through the recursion..."into" or "out of" so to speak. — Philluminati, Mar 16 '11 at 19:06
Yes, you could use the same algorithm and pretend to be the interpreter and manage your own stack. Alternatively, you could come up with an iterative algorithm for generating permutations, which would be easier to express as a loop. — nmichaels, Mar 16 '11 at 19:08
Is there a reason you want to do this? Is this purely educational? Any recursive function *can* be implemented without recursion (because ultimately recursion *is* iteration), but not every recursive algorithm *should* be implemented iteratively. Recursion is the natural way of expressing many algorithms. — Glenn Maynard, Mar 16 '11 at 19:18
@Glenn Maynard: I'm trying to write, in C, a program that solves a specific problem which hasn't been solved before (for a popular tv game show). I believe I can solve the problem using a brute force approach so I'm trying to see if I can do it! And doesn't C have a stack limit? My search space is enormous! — Philluminati, Mar 16 '11 at 20:26

score 3 · Answer 1 · answered Mar 16 '11 at 19:13

3

The most pythonic way of doing permutations is to use:

>>> from itertools import permutations
>>> permutations([1,2,3])
>>> list(permutations([1,2,3]))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

answered Mar 16 '11 at 19:13

fabrizioM

46,639
15
102
119

And the docs of that function show how to generate permutations iteratively: http://docs.python.org/py3k/library/itertools#itertools.permutations – ncoghlan Mar 16 '11 at 19:26
This doesn't seem to work for me. I can import itertools in Python 2.5.2 but I don't have a permutations function – Philluminati Mar 16 '11 at 19:29
@Philluminati is from version 2.6 – fabrizioM Mar 16 '11 at 20:53

thomson_matt · Answer 2 · 2011-03-17T11:11:26.803

Let's say you want to find all permutations of [1, 2, 3, 4]. There are 24 (=4!) of these, so number them 0-23. What we want is a non-recursive way to find the Nth permutation.

Let's say we sort the permutations in increasing numerical order. Then:

Permutations 0-5 start with 1
Permutations 6-11 start with 2
Permutations 12-17 start with 3
Permutations 18-23 start with 4

So we can get the first number of permutation N by dividing N by 6 (=3!), and rounding up.

How do we get the next number? Look at the second numbers in permutations 0-5:

Permutations 0-1 have second number 2.
Permutations 2-3 have second number 3.
Permutations 4-5 have second number 4.

We see a similar thing with permutations 6-11:

Permutations 6-7 have second number 1.
Permutations 8-9 have second number 3.
Permutations 10-11 have second number 4.

In general, take the remainder after dividing by 6 earlier, divide that by 2 (=2!), and round up. That gives you 1, 2, or 3, and the second item is the 1st, 2nd or 3rd item left in the list (after you've taken out the first item).

You can keep going in this way. Here's some code that does this:

from math import factorial

def gen_perms(lst):
    all_perms = []

    # Find the number of permutations.
    num_perms = factorial(len(lst))

    for i in range(num_perms):
        # Generate the ith permutation.
        perm = []
        remainder = i

        # Clone the list so we can remove items from it as we
        # add them to our permutation.
        items = lst[:]

        # Pick out each item in turn.
        for j in range(len(lst) - 1):
            # Divide the remainder at the previous step by the
            # next factorial down, to get the item number.
            divisor = factorial(len(lst) - j - 1)
            item_num = remainder / divisor

            # Add the item to the permutation, and remove it
            # from the list of available items.
            perm.append(items[item_num])
            items.remove(items[item_num])

            # Take the remainder for the next step.
            remainder = remainder % divisor

        # Only one item left - add it to the permutation.
        perm.append(items[0])

        # Add the permutation to the list.
        all_perms.append(perm)

    return all_perms

score 0 · Accepted Answer · answered Mar 16 '11 at 19:09

0

I am not too familiar with the python syntax, but the following code (in 'c') shouldn't be too hard to translate assuming python can do nested for statements.

int list[3]={1,2,3};
int i,j,k;

for(i=0;i < SIZE;i++)
for(j=0;j < SIZE;j++)
for(k=0;k < SIZE;k++)
if(i!=j && j!=k && i!=k)
printf("%d%d%d\n",list[i],list[j],list[k]);

answered Mar 16 '11 at 19:09

Adam

707
1
7
15

Does this only work because you have one index for each number....i.e. if the list was size 4 would I need another loop? – Philluminati Mar 16 '11 at 20:28
Yes, this will only work if you have a list size of 3. I apologize for such a late comment. – Adam Mar 17 '11 at 02:58

How to rewrite a recursive function to use a loop instead?

3 Answers3

Linked