Using recursion to concatenate two strings-CodePudding

My goal is to concatenate two strings using recursion.

The input would be str1 = ("long string") str2 = ("yes so long")

and the output would be: 'lyoensg ssto rlionngg'

Assumptions are that both strings are the same length.

My code as of now is:

def concat_order(str1, str2):
    if len(str1) == 0:
        return 'complete'
    i = 0
    new_str = str1[i]   str2[i]
    i = i   1
    return concat_order(str1[1:], str2[1:])
    return new_str
print(concat_order("long string"', "yes so long"))

Im sure Im no where close but I am struggling with making it loop.

I am not allowed to use loops but I can use if statements

CodePudding user response：

Recursion just needs a base case and a recursion case. Here your base case is a little strange. You never want the string "complete" so you shouldn't return that. The base case when str1 is empty should just return the empty string.

Then you just need to take the first letter from each string, concat, and concat with recursion of the rest:

def concat_order(str1, str2):
    if len(str1) == 0:
        return ''
    
    a, b = str1[0], str2[0]
    
    return a   b   concat_order(str1[1:], str2[1:])
   

concat_order("long string", "yes so long")
# 'lyoensg  ssot rlionngg'

Note the extra space is the correct behavior unless there's a requirement to prevent them.

CodePudding user response：

You don't need to pass 'i' like this: new_str = str1[i] str2[i] as you are already returning string excluding previous character: return concat_order(str1[1:], str2[1:]). Also a function can not have two return statements like this:

    return concat_order(str1[1:], str2[1:])
    return new_str

any statement after return statement won't execute. That's why we write multiple return statements in some conditional statement like if else

Modified your program to give correct answer.

def concat_order(str1, str2, new_str):
    if len(str1) == 0:
        return new_str
    new_str  = str1[0]   str2[0]

    return concat_order(str1[1:], str2[1:], new_str)

ans = ""
print(concat_order("long string", "yes so long", ans))

or you can do this:

def concat_order(str1, str2):
    if len(str1) == 0:
        return ''
        
    return str1[0]   str2[0]   concat_order(str1[1:], str2[1:])

print(concat_order("long string", "yes so long"))

as the control flow reaches base case, we have alreay what we wanted so don't return anything.

CodePudding user response：

def concat_strings_rec(str1, str2):
    if len(str1) < 1:
        return ""
    else:
        curStr = str1[0]   str2[0]
        return curStr   concat_strings_rec(str1[1:], str2[1:])


def concat_string_iter(str1, str2):
    return "".join([str1[i]   str2[i] for i in range(len(str1))])


string1 = "long string"
string2 = "yes so long"

print(concat_strings_rec(string1, string2))
print(concat_string_iter(string1, string2))

Expected output:

lyoensg  ssot rlionngg
lyoensg  ssot rlionngg

Recursive solution

You need the base case which is when the array length is 0. In that case return an empty string. In all other cases return the first element of each string concatenated with the return value of the recursive call to concat_strings_rec(). Remember to decrease the array size for the recursive calls!

Iterative solution

The iterative solution just loops through the array concatenating each character within the two strings and putting the concatenated first, second, third,... character in an array. Then use "".join() to concatenate those two character strings in the array to a complete string.

Recommendation

Don't use the recursive solution as it just consumes more memory due to the call stack and it will be slower and since Python has a limit on the number of calls on the call stack it will fail for larger strings.