Stephan - 1 month ago 10
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:

`````` merge_chars('abxy','lmz')
``````

returns

``````'ablmxyz'.
``````

using recursion is a requirement.

however, when my function calls

``````merge_chars('ace','bdf')
``````

it returns

``````aaaace
``````

``````abcdef
``````

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
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?

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)
else:
return b[0] + merge_chars(a, b[1:])

CASES = [
('ace', 'bdf'),
('abc', 'xyz'),
('abxy', 'lmzzz'),
('acdeghilmnosu', 'bfjkpqrtvwxyz'),
('cdefghijklmnpqrstuvw', 'aboxyz')
]

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

Output:

``````ace & bdf -> abcdef
abc & xyz -> abcxyz
abxy & lmzzz -> ablmxyzzz
acdeghilmnosu & bfjkpqrtvwxyz -> abcdefghijklmnopqrstuvwxyz