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
– Philluminati, Commented Mar 16, 2011 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
– nmichaels, Commented Mar 16, 2011 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
– Glenn Maynard, Commented Mar 16, 2011 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
– Philluminati, Commented Mar 16, 2011 at 20:26

fabmilo · Accepted Answer · 2011-03-16 19:13:29Z

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, 2011 at 19:13

fabmilo

48.5k16 gold badges108 silver badges123 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

ncoghlan Over a year ago

And the docs of that function show how to generate permutations iteratively: docs.python.org/py3k/library/itertools#itertools.permutations

Philluminati Over a year ago

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

fabmilo Over a year ago

@Philluminati is from version 2.6

thomson_matt · Accepted Answer · 2011-03-17 11:11:26Z

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

Adam · Accepted Answer · 2011-03-16 19:09:10Z

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, 2011 at 19:09

Adam

7171 gold badge7 silver badges15 bronze badges

2 Comments

Philluminati Over a year ago

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?

Adam Over a year ago

Yes, this will only work if you have a list size of 3. I apologize for such a late comment.

Collectives™ on Stack Overflow

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

3 Answers 3

3 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related