Как можно изменить код, чтобы решить задачу при помощи рекурсии?

Question

Я написал программу для поиска палинграм в текстовом файле, состоящим из 100 тысяч слов. Каким образом можно ее изменить, чтобы эта же задача решалась с использованием рекурсии? Я прорешал много других задачек связанных с рекурсией, чтобы лучше ее понять, но в данной задаче решение в голову никак не приходит.

Для справки: Палинграмма - то же, что и палиндром, но состоит из нескольких слов и также читается одинаково слева направо.

Например: drowsy sword, denims mined, dairy raid, rise sir

import dictionary

word_list = dictionary.load("words.txt")

def find_palingrams():
    pali_list = []
    words = set(word_list)

    for word in words:
        end = len(word)
        rev_word = word[::-1]

        if end > 1:

            for i in range(end):

                # Является ли КОНЕЦ слова палиндромным, а НАЧАЛО -
                # перевернутым словом в списке слов (реальным словом)
                if word[i:] == rev_word[:end - i] and rev_word[end - i:] in words:
                    pali_list.append((word, rev_word[end - i:]))

                # Является ли НАЧАЛО слова палиндромным, а КОНЕЦ -
                # перевернутым словом в списке слов (реальным словом)
                if word[:i] == rev_word[end - i:] and rev_word[:end - i] in words:
                    pali_list.append((rev_word[:end - i], word))

    return pali_list

palingrams = find_palingrams()

Answer 1

чисто из спортивного интереса можно заменить внутренний цикл на рекурсию, тогда получится что-то такое:

def find_palingrams():
    pali_list = []
    words = set(word_list)
    
    def pali(suff, pref=''):
        if not suff: return None
        if pref[::-1] in words and suff==suff[::-1]: return pref+suff,pref[::-1]
        if suff[::-1] in words and pref==pref[::-1]: return suff[::-1],pref+suff
        return pali(suff[1:],pref+suff[0])
    
    for word in words:
        if p:=pali(word): pali_list.append(p)
                
    return pali_list


word_list = ['drowsy', 'sword', 'denims', 'mined', 'dairy', 'riad', 'rise', 'sir']
find_palingrams()
# [('rise', 'sir'), ('denims', 'mined'), ('drowsy', 'sword'), ('dairy', 'riad')]

как видно, лучше и короче не стало, а читабельность кода пострадала

БЛОГ НА HUSL

Как можно изменить код, чтобы решить задачу при помощи рекурсии?

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