Explanation of Recursive Function in Python

Question

I am new to Python and trying to wrap my head around recursive functions. I am understanding the overall concept but I came across an example that I can't seem to understand fully what it is doing. A step by step breakdown of what is happening would be ideal, appreciate the help in advance.

def anagrams(s):
 if s == '': 
 return [s]
 else:
 ans = []
 for w in anagrams(s[1:]): 
 for pos in range(len(w)+1):
 ans.append(w[:pos] + s[0] + w[pos:])
 return ans 

• Elliott Frisch: Psst! I hear you're having trouble with recursion. Just read this until you understand.
• Matt Messersmith: @ElliottFrisch literally dying, well played my good sir
• Klaus D.: There are three things to know about recursion: 1. how recursion works 2. that you don't use it if there is an other way and 3. there's always an other way.

Answer 1

if s == '': 
 return [s]

If it is a blank string, there are no other anagrams, return a list with only that blank string..

Otherwise,

for w in anagrams(s[1:]):

separate s to the first character (s[0]) and the substring of all other characters (s[1:]). Call the function again to find all anagrams of the substring (those are the ws),

for pos in range(len(w)+1):
 ans.append(w[:pos] + s[0] + w[pos:])

then for each of those, insert the first character of s in any possible position (pos) within w.

Here is your function with a little print statement that helps to see whats going on.

def anagrams(s):
 if s == '': 
 return [s]
 else:
 ans = []
 level = len(s)
 for w in anagrams(s[1:]):
 print('level %d, s[0]: %s, w: %s' % (level, s[0], w))
 for pos in range(len(w)+1): 
 ans.append(w[:pos] + s[0] + w[pos:])
 return ans 

try:

1.

anagrams('a')

output:

level 1, s[0]: a, w: 

2.

anagrams('ba')

output:

level 1, s[0]: a, w: 
level 2, s[0]: b, w: a

3.

anagrams('cba')
level 1, s[0]: a, w: 
level 2, s[0]: b, w: a
level 3, s[0]: c, w: ba
level 3, s[0]: c, w: ab

Answer 2

def anagrams(s):
 # if argument <s> is a blank String
 if s == '':
 # return a list is just <s> in it
 return [s]
 else:
 # create a List
 ans = []
 # for each String character in calling this function recursively,
 # but removing character 0!
 for w in anagrams(s[1:]): 
 # for character position number starting at 0 and ending at
 # the length of the returned value of the recursed function
 # plus 1
 for pos in range(len(w)+1):
 # append a string with the following concatenation:
 # - the returned value's string from position 0 to position <pos>
 # - the character at position 0 of <s>
 # - the returned value's string from position <pos> to the end
 ans.append(w[:pos] + s[0] + w[pos:])
 # return the list
 return ans