Как генерировать чередующиеся подстроки с помощью рекурсии

Question

У меня есть практический вопрос, который требует от меня генерирования x числа чередующихся подстрок, а именно "# -" и "# -", используя как рекурсию, так и итерацию. Eg.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

Answer 1

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

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)

Answer 2

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

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

Answer 3

Для рекурсивного решения вам нужен базовый случай и повторный вызов функции с другим значением, чтобы в конце вы получили желаемый результат. Здесь мы можем решить эту проблему рекурсивно, как - 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: #-#--#-