Ревью кода и замена рекурсии на итерацию

Question

Многие знают игру "Слова"

Правила простые: задаётся некоторое первое слово, а каждое следующее начинается с буквы, на которую заканчивается текущее слово. При том запрещено использовать слова, которые уже имели место быть.

Например, арбуз - заяц - цапля - яйцеклетка - ... (арбуз использовать снова нельзя)

Пусть цепочка - это список слов, последовательно использованных в очередной игре (очевидно, что этот список рано или поздно закончится)

Решил написать программу, которая из некоторого списка слов WORDS, получает список всевозможных цепочек. Например, если

WORDS = ['sana', 'apple', 'rock', 'key', 'agregator', 'roll', 'kite']

то список всевозможных цепочек будет иметь следующий вид

[
    ['apple'], 
    ['key'], 
    ['roll'], 
    ['kite'], 
    ['sana', 'apple'], 
    ['rock', 'key'],
    ['rock', 'kite'], 
    ['agregator', 'roll'], 
    ['sana', 'agregator', 'roll'], 
    ['agregator', 'rock', 'key'], 
    ['agregator', 'rock', 'kite'], 
    ['sana', 'agregator', 'rock', 'key'],
    ['sana', 'agregator', 'rock', 'kite']
]

Вот собственно код программы. Делал через рекурсию. Функция f()

WORDS = ['sana', 'apple', 'rock', 'key', 'agregator', 'roll', 'kite']

USED_WORDS = []

RESULT = []

# функция возвращает список всех слов из WORDS, которые начинаются на букву, на которую заканчивается текущее слово curr
def get_words(curr):
    return list(filter(lambda word: word[0] == curr[-1], WORDS))


def f(curr):
    global RESULT

    words = get_words(curr)

    USED_WORDS.append(curr)

    # избавиться от уже использованных слов
    # words = list(set(words) - set(USED_WORDS))
    words = [word for word in words if word not in USED_WORDS]

    # если список новых слов не пуст
    if words:
        for word in words:
            f(word)
    else:
        # цепочка получена
        RESULT.append(USED_WORDS.copy())

    # не забыть, что при выходе из рекурсии текущее слово уже не считается использованным
    USED_WORDS.pop()


if __name__ == '__main__':
    for word in WORDS:
        f(word)

    RESULT.sort(key=len)
    print(RESULT)

Так вот... у меня есть несколько вопросов.

Является ли моя реализация задуманного алгоритма верной? Ахаха)) ну. то есть буквально: не упустил ли я что-либо при реализации?
Если всё верно, то меня терзают смутные сомнения насчёт рекурсии. План у меня грандиозный: в WORDS положить целый словарь существительных английского языка. А это порядка 200К слов! И ведь мне хочется, чтобы программа не просто сработала так быстро, насколько это в приницпе возможно, но и чтобы она не опрокинулась с ошибкой о максимальной глубине рекурсии (а это обязательно произойдёт). Поэтому мне интересно, как можно заменить рекурсию на итеративный подход? (Слышал о теореме Клини о рекурсии, но не думаю, что знание её доказательства мне поможет)

Спасибо за вашу помощь!

Answer 1

Code style fix

Не надо именовать переменные capslock'ом, capslock — для констант.
Именнуйте функции более осмысленно (это же не математика, а то f...)
Комментарии функции добавляйте внутрь функции:

Wrong ❌:

# функция возвращает список всех слов из WORDS, которые начинаются на букву, на которую заканчивается текущее слово curr
def get_words(curr):

    return list(filter(lambda word: word[0] == curr[-1], WORDS))

Right ✅:


def get_words(curr):
    '''функция возвращает список всех слов из WORDS, которые начинаются на букву, на которую заканчивается текущее слово curr'''
    return list(filter(lambda word: word[0] == curr[-1], WORDS))

Вместо рекурсии подойдет цикл, но он тоже сильно юзает стековое пространство.

from pprint import pprint
words = ['sana', 'apple', 'rock', 'key', 'agregator', 'roll', 'kite']
out = []
for i in words:
    last = i[-1]
    found = 0
    for word in words:
        if word[0] == last:
            out.append([i, word])
            found = 1
    if not found:
       out.append([i])


pprint(sorted(out))

Answer 2

words = ['some_word', 'some_word', 'some_word', ...]
check_word = 'another_word'
right_words = [word for word in words if word.startswith(check_word[-1])]
# или если хотите только уникальные значения то 
right_words = set(word for word in words if word.startswith(check_word[-1]))

Я ничего не упустил?

БЛОГ НА HUSL

Ревью кода и замена рекурсии на итерацию

Ответы (2 шт):

Code style fix

Вместо рекурсии подойдет цикл, но он тоже сильно юзает стековое пространство.