CODEWITHSUNDEEP
pythonfor-looprecursion
Stephen Farrell
Stephen Farrell

Reputation: 33

For loop in recursive function?

When the for loop runs, why does it print all permutations of ABC instead of all 'A's?

def perm(l, n, str_a):
    if len(str_a) == n:
        print str_a
    else:
        for c in l:
            perm(l, n, str_a+c)


perm("ABC", 3, "")

Prints:

AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB BBC BCA BCB...

Upvotes: 2

Views: 401

Answers (3)

brandonsimpkins
brandonsimpkins

Reputation: 574

I have no idea what you are trying to do, but maybe a little bit of debug output would help you figure it out. Try this: 

def perm(iter, l, n, str_a):
    print "starting iteration {0}: l='{1}', n='{2}', str_a='{3}'".format(
        iter, l, n, str_a)
    if len(str_a) == n:
        print str_a
    else:
       for c in l:
           perm(iter+1, l, n, str_a+c)

perm(1, "ABC", 3, "")

Upvotes: 0

Giulio Franco
Giulio Franco

Reputation: 3230

It does not keep printing 'A's, because, after 3 recursions, it will have formed the string "AAA". Then, the line print str_a will be executed, as the condition len(str_a) == n will be verified.

After that, the execution will go back to the callee function, which was inside the c loop. c had value "A". At the following iteration, c will get value "B", and perm("ABC", 3, "AAB") will be invoked, printing "AAB", and so on.

Maybe the recursion graph could clearen things up (it's incomplete, because it's big)Recursion graph (incomplete)

Upvotes: 1

Tim Pietzcker
Tim Pietzcker

Reputation: 336478

  1. When you call perm("ABC", 3, ""), the else clause is executed (because len("") != 3).
  2. This result in the calls perm("ABC", 3, "A"), perm("ABC", 3, "B") and perm("ABC", 3, "C"). Let's see what happens with the first one:
  3. Again, the else is executed, resulting in the function calls perm("ABC", 3, "AA"), perm("ABC", 3, "AB") and perm("ABC", 3, "AC").
  4. The same thing happens with the other function calls from step 2 (you get the idea).
  5. Let's look at perm("ABC", 3, "AA"): When called, the else is executed yet again --> perm("ABC", 3, "AAA"), perm("ABC", 3, "AAB") and perm("ABC", 3, "AAC").
  6. In these calls, the expression len(str_a) finally is == 3, which means that str_a will be printed.
  7. And so on, until CCC.

Upvotes: 2

Related Questions