The variables at each call frame level are independent and reestablished after returning from a sub call.

The for loop at level 3 calls the recursion at level 4 each time twice before returning to level 2

   3:ab    # for @set=(c,d); return to 2 

    4:abc  # ...

    4:abd  # ...
[download]

Level 4 calls level 5 once and returns to 3

 
    4:abc    # for @set=(d); return to 3

     5:abcd  # print result; return to 4


# ... later


    4:abd    # for @set=(c); return to 3

     5:abdc  # print result; return to 4
[download]

update

> But I am not following the logic of how it then goes from $perm = abcd and @set=[] to $perm = abd and @set=c, or how $level went from 5 back to 4.

• ...
• 5 printed "abcd" and returned to 4;
• 4's loop over (d) was exhausted and returned to 3;
• 3 looping over (c,d) stepped to the second element and called 4, i.e. perm("abd", "c")
• 4 loops over (c) and calls 5;
• 5 printed "abdc" and returned to 4;
• ...

HTH :)

update

Bill's remark is spot on, the explicit "return" is fake, the real return happens implicitly after the loop.