Как создать генератор для рекурсивного метода на Python?

Question

Задача. Есть рекурсивная функция, которая возвращает числа по формуле: an = (an-2 + 1) * an-1, где a0 = 0 и a1 = 1

Код функции:

def dummy_numbers(number):
    if number == 0:
        return 0
    elif number == 1:
        return 1
    else:
        # an = (an-2 + 1)×an-1
        return (dummy_numbers(number - 2) + 1) * dummy_numbers(number - 1)

print(dummy_numbers(5))

Сейчас работает так:

Ввёл 0, вывело 0,

ввёл 1, вывело 1,

ввёл 2, вывело 1,

ввёл 3, вывело 2,

ввёл 4, вывело 4,

ввёл 5, вывело 12

А надо сделать так, чтобы написав код:

for i in dummy_numbers(5):
    print(i)

Выводило: 0, 1, 1, 2, 4, 12

Если сделать замену return на yield:

def dummy_numbers(number):
    if number == 0:
        yield 0
    elif number == 1:
        yield 1
    else:
        # an = (an-2 + 1)×an-1
        yield (dummy_numbers(number - 2) + 1) * dummy_numbers(number - 1)

for i in dummy_numbers(5):
    print(i)

То ОШИБКА:

yield (dummy_numbers(number - 2) + 1) * dummy_numbers(number - 1)
TypeError: unsupported operand type(s) for +: 'generator' and 'int'

Нужно именно написать генератор для рекурсивного метода. Знаю, что нужно вместо return использовать yield, но никак не могу понять как это примениь к моей рекурсивной функции.

Помогите пожалуйста, не могу разобраться.

Answer 1

Чтобы генератор выводил числа 0, 1, 1, 2, 4, 12, функция сама должна используя yield в цикле, вызывать другую функцию, которая будет выдавать эти числа. Уж рекурсивная она или какая - не важно (использование yield в самой рекурсии не имеет смысла).

def dummy_number(n):
    if n in (0, 1):
        return n

    return (dummy_number(n - 2) + 1) * dummy_number(n - 1)


def dummy_numbers(up_to): # Генератор - отдельно.
    for k in range(up_to + 1):
        yield dummy_number(k)


for i in dummy_numbers(5):
    print(i)

Рекурсия, конечно, в этом случае уместна только в учебных целях. Гораздо эффективнее будет выводить числа, запоминая последние два в отдельных переменных. Чтобы каждый раз заново не находить a(n - 2), a(n - 1)

БЛОГ НА HUSL

Как создать генератор для рекурсивного метода на Python?

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