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

Psst! I hear you're having trouble with recursion. Just read this until you understand. — Elliott Frisch
– Elliott Frisch, Commented Oct 4, 2018 at 3:30
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. — Klaus D.
– Klaus D., Commented Oct 4, 2018 at 3:42

Yosi Hammer · Accepted Answer · 2018-10-04 04:10:47Z

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

Josh Austin · Accepted Answer · 2018-10-04 03:51:25Z

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

Collectives™ on Stack Overflow

Explanation of Recursive Function in Python

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related