CODEWITHSUNDEEP
pythonrecursion
cisco
cisco

Reputation: 121

Explanation of Recursive Function in Python

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

Upvotes: 0

Views: 240

Answers (2)

Yosi Hammer
Yosi Hammer

Reputation: 588

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

Upvotes: 1

Josh Austin
Josh Austin

Reputation: 21

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

Upvotes: 1

Related Questions