Python Forum

Full Version: Please help explaining this recursive function
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Hi, I am learning Python and now I am having trouble with a recursive generator. I could not seem to trace how it works regardless of many print statements.

def heap_perm(n, A):      
    print('outside loop 01: n=%d'%n)
    if n == 1: 
        yield A     
        print('outside loop 02: n=%d'%n)
    else:
        print('outside loop 03: n=%d'%n)
        for i in range(n-1):            
            print('inside loop 01: n=%d, i=%d'%(n,i))
            for hp in heap_perm(n-1, A):
                print('inside loop 02: n=%d, i=%d'%(n,i))
                yield hp
                print('inside loop 03: n=%d, i=%d'%(n,i))
            print('inside loop 04: n=%d, i=%d'%(n,i))
            j = 0 if (n % 2) == 1 else i 
            print('inside loop 05: n=%d, i=%d'%(n,i))
            A[j],A[n-1] = A[n-1],A[j]
            print('inside loop 06: n=%d, i=%d'%(n,i))
        print('inside loop 07: n=%d, i=%d'%(n,i))
        for hp in heap_perm(n-1, A): 
            print('inside loop 08: n=%d, i=%d'%(n,i))
            yield hp
            print('inside09: n=%d, i=%d'%(n,i))
When I tried to see the process,

for n = 3 and A = [1,2,3],

I seem to understand how i works for the first round. The result looks like this.

outside loop 01: n=3
outside loop 03: n=3
inside loop 01: n=3, i=0
outside loop 01: n=2
outside loop 03: n=2
inside loop 01: n=2, i=0
outside loop 01: n=1
inside loop 02: n=2, i=0
inside loop 02: n=3, i=0

k= [1, 2, 3]


1. How does n increase back to 3?

When I looked into the second round, I am more confused.

inside loop 03: n=3, i=0
inside loop 03: n=2, i=0

outside loop 02: n=1
inside loop 04: n=2, i=0
inside loop 05: n=2, i=0
inside loop 06: n=2, i=0
inside loop 07: n=2, i=0
outside loop 01: n=1
inside loop 08: n=2, i=0
inside loop 02: n=3, i=0
k= [2, 1, 3]


2. I have no idea why n is reduced again.
3. When it jumped to inside loop 04, why does n increase to 2?

If anyone could please explain me, or provide a better way rather than using print statements, that will be great.
Thanks very much.
This wikipedia page may help, I think.
This algorithm is to generate all arrangments of the List Elements.
Since its, a recursive generator function it is difficult to visualise it via print statements.
I'd suggest you either use THIS to visualise or use an IDE debugger and set breakpoints to get a better idea.
(Nov-13-2018, 02:24 PM)Gribouillis Wrote: [ -> ]This wikipedia page may help, I think.

Thanks a lot.

(Nov-13-2018, 02:35 PM)hbknjr Wrote: [ -> ]This algorithm is to generate all arrangments of the List Elements.
Since its, a recursive generator function it is difficult to visualise it via print statements.
I'd suggest you either use THIS to visualise or use an IDE debugger and set breakpoints to get a better idea.

This website is of great help.

Thanks very much !