Нужна помощь в создании чередующихся подстрок с помощью рекурсии

У меня есть практический вопрос, который требует, чтобы я сгенерировал x количество чередующихся подстрок, а именно "# -" и "# -", используя как рекурсию, так и итерацию. Например, string_iteration (3) генерирует "# - # - # -". Я успешно реализовал решение для итеративного метода, но у меня возникли проблемы с началом рекурсивного метода. Любые указатели, пожалуйста?

Итерационный метод

def string_iteration(x):
    odd_block = '#-'
    even_block = '#--'
    current_block = ''
    if x == 0:
        return ''
    else:
        for i in range(1,x+1):
            if i % 2 != 0:
                current_block += odd_block
            elif i % 2 == 0:
                current_block += even_block
            i += 1
        return current_block

Всего 3 ответа


Для рекурсии вам почти всегда нужен базовый случай и все остальное. Здесь ваш базовый случай довольно прост - когда x <1, вы можете вернуть пустую строку:

if x < 1:
    return '' 

После этого вам просто нужно вернуть блок + результат string_iteration(x-1) . После этого остается только решить, какой блок выбрать. Например:

def string_iteration(x):
    # base case
    if x < 1:      
        return '' 

    blocks = ('#--', '#-')
    # recursion
    return string_iteration(x-1) + blocks[x % 2] 

string_iteration(5)
# '#-#--#-#--#-'

Это сводится к

string_iteration(1) + string_iteration(2) ... string_iteration(x)

Другой ответ не дает того же результата, что и ваш итерационный метод. Если вы всегда хотите, чтобы он начинался с нечетного блока, вы должны добавить блок справа от рекурсивного вызова вместо левого:

def string_recursion(x):
    odd_block = '#-'
    even_block = '#--'
    if x == 0:
        return ''
    if x % 2 != 0:
        return string_recursion(x - 1) + odd_block
    elif x % 2 == 0:
        return string_recursion(x - 1) + even_block

Для рекурсивного решения вам нужен базовый случай и повторный вызов функции с другим значением, чтобы в конце вы получили желаемый результат. Здесь мы можем решить эту проблему рекурсивно, как - string_recursive(x) = string_recursive(x-1) + string_recursive(x-2) + ... + string_recursive(1) .

def string_recursion(x, parity):
    final_str = ''
    if x == 0:
        return ''
    if parity == -1: # when parity -1 we will add odd block
        final_str += odd_block
    elif parity == 1:
        final_str += even_block
    parity *= -1    # flip the parity every time
    final_str += string_recursion(x-1, parity)
    return final_str

odd_block = '#-'
even_block = '#--' 
print(string_recursion(3, -1)) # for x=1 case we have odd parity, hence -1
# Output: #-#--#-

Есть идеи?

10000