Stephan Stephan - 9 months ago 41
Python Question

recursion function that takes two str return a sorted str

def merge_chars(a : str, b : str) -> str:
if a == '':
return b
if b == '':
return a

for x in a:
for y in b:
if x > y:
return y + merge_chars(a[1:],b)
elif x < y:
return x + merge_chars(a,b[1:])

This function takes two str, and return a str in alphabetic order. for example:




using recursion is a requirement.

however, when my function calls


it returns


instead of


the error I got is listed below:

39 # Test merge_chars
43 *Error: merge_chars('ace','bdf') -> aaaace but should -> abcdef
44 *Error: merge_chars('abc','xyz') -> aaaabc but should -> abcxyz
45 *Error: merge_chars('abxy','lmzzz') -> aaaaaabxy but should -> ablmxyzzz
46 *Error: merge_chars('acdeghilmnosu','bfjkpqrtvwxyz') -> aaaaaaaaaaaaaacdeghilmnosu but should -> abcdefghijklmnopqrstuvwxyz
47 *Error: merge_chars('bcgprvyz','adefhijklmnoqstuwx') -> aaaaaaaaadefhijklmnoqstuwx but should -> abcdefghijklmnopqrstuvwxyz
48 *Error: merge_chars('cdefghijklmnpqrstuvw','aboxyz') -> aaaaaaaaaaaaaaaaaaaaaboxyz but should -> abcdefghijklmnopqrstuvwxyz
51 *Error: merge_chars(''.join(sorted(l[:13])), ''.join(sorted(l[13:]))) -> aaaaaaaaaaaaaabcdgjlnpqrtz but should -> abcdefghijklmnopqrstuvwxyz

can someone tell me how to fix it?

Answer Source

If you want to use recursion you don't need to use loops. Instead just remove one character on each call and then recurse. You just need to make sure that everyone of following three scenarios are covered:

  1. Neither of the strings have characters left
  2. Only one of the strings has characters left
  3. Both strings have characters left

Here's example:

def merge_chars(a, b):
    # Base case
    if not a and not b:
        return ''

    if a and (not b or a[0] <= b[0]):
        return a[0] + merge_chars(a[1:], b)
        return b[0] + merge_chars(a, b[1:])

    ('ace', 'bdf'),
    ('abc', 'xyz'),
    ('abxy', 'lmzzz'),
    ('acdeghilmnosu', 'bfjkpqrtvwxyz'),
    ('bcgprvyz', 'adefhijklmnoqstuwx'),
    ('cdefghijklmnpqrstuvw', 'aboxyz')

for x, y in CASES:
    print('{} & {} -> {}'.format(x, y, merge_chars(x, y)))


ace & bdf -> abcdef
abc & xyz -> abcxyz
abxy & lmzzz -> ablmxyzzz
acdeghilmnosu & bfjkpqrtvwxyz -> abcdefghijklmnopqrstuvwxyz
bcgprvyz & adefhijklmnoqstuwx -> abcdefghijklmnopqrstuvwxyz
cdefghijklmnpqrstuvw & aboxyz -> abcdefghijklmnopqrstuvwxyz