Преобразование итерационного решения в рекурсивное решение

Question

В настоящее время я работаю над проблемой, которая требует, чтобы я спроектировал функцию, которая принимает строку «0», «1» и «X» в качестве аргумента и возвращает генератор, который выдает различные комбинации X, обращенные в «1» и «X». 0's

ie: если передать '0XX1', будет возвращен генератор, который выдаст-> 0001, 0101, 0011, 0111,

Я решил проблему итеративно, но нужно уметь чтобы решить это рекурсивно. Каков наилучший способ решения этой проблемы? В такой сложной проблеме (ну, как мне сложно!), Как мне определить базовый случай и рекурсивный случай?

Ниже приведено мое итеративное решение:

from typing import Generator
def binary_strings(string: str) -> Generator[str, None, None]:



    listOfIndices = []
    starterString = ''
    for index, char in enumerate(string):
    if char == 'X':
        starterString = starterString + '0'
        listOfIndices.append(index)

    else:
        starterString = starterString + char

    def stringGenerator(): #generates the different combos
    baseString = starterString
    moddedString = ''
    n = len(listOfIndices)
    counter = 1

    for i, character in enumerate(
            starterString):
        if i == 0:
            yield starterString
        else:
            break

    while counter <= n:

        for i, chara in enumerate(baseString):
            if i in listOfIndices:
                moddedString = baseString[:i] + '1' + baseString[i + 1:]
                yield moddedString
                counter += 1
                if counter > n and n >= 1:
                    counter = 1
                    n -= 1
                    baseString = moddedString
                    break
                else:
                    continue

return stringGenerator()

Answer 1

Часто бывает так, что рекурсивные функции проще рассуждать и короче. Обычно вы начинаете с базового варианта. Здесь вы можете представить, что ваша функция должна давать с пустой строкой. Вероятно, ''.

Далее, если ваш первый символ не является X, вы просто получите этот первый символ плюс результат рекурсивного вызова остальных. Если это равно и X, то вы выдаете как 1 + рекурсивный вызов , так и 0 + рекурсивный вызов. Что-то вроде:

def combos(s):
    if len(s) == 0:
        yield  ''
        return 

    head, *tail = s
    for combo in combos(tail):
        if head == 'X':
            yield '1'+ combo
            yield '0'+ combo
        else:
            yield head + combo

s = '0XX1'
list(combos(s))

#['0111', '0011', '0101', '0001']

Answer 2

Игнорирование (тривиального) базового случая (то есть, когда нет заменяющих X), binary_strings(s) = binary_strings(s') + binary_strings(s''), где s' равно s с первым X, замененным на 0, и s'' is s с первым X, замененным на 1.