Блог

Главная - Вопросы по программированию - Повторение в ряду Фибоначчи с рекурсией

Повторение в ряду Фибоначчи с рекурсией

#python #recursion

#python #рекурсия

Вопрос:

Я пытаюсь написать метод, который печатает первые n fibonacci ряды чисел с использованием рекурсии. Я не хочу писать метод, а затем создавать отдельный цикл после метода для распечатки первой n fibonacci серии. Я попытался использовать try и finally блокировать, так как знаю finally , что оператор всегда будет выполняться. Вывод fibonacci серии работает нормально, но продолжает повторяться. Возможно ли остановить повторение?

 def fibonacci(n):
    if n <= 1:
        return n
    try:
        fib = fibonacci(n-1)   fibonacci(n-2)
        return fib
    finally:
        print("F{} = {}".format(n, fib))
    
fibonacci(6)

вывод

 F2 = 1
F3 = 2
F2 = 1
F4 = 3
F2 = 1
F3 = 2
F5 = 5
F2 = 1
F3 = 2
F2 = 1
F4 = 3
F6 = 8

Комментарии:

1. «Я не хочу писать метод, а затем создавать отдельный цикл после метода для распечатки первых n рядов Фибоначчи» почему?

2. Рекурсия заставляет вас рекурсивно пересчитывать 2 значения на каждом этапе. Итак, помещение вашего оператора печати в вашу рекурсивную функцию отображает некоторые вещи, которые вы не хотите видеть. Я бы сгенерировал значения и отобразил результат в другом месте.

3. так что это так. вы можете попробовать с помощью dp memo. установите значение dict, затем выведите dict.

4. @MetallimaX звучит полезно. Я мог бы просто сформировать отдельный цикл снаружи. Просто интересно, есть ли лучший способ

5. @deadshot Это то, что делают все. Просто пытаюсь понять, есть ли лучший способ

Ответ №1:

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

 def fibonacci(n):
    if n <= 0:
        return 1, 1
    try:
        nxt, fib = fibonacci(n-1)
        return nxt fib, nxt
    finally:
        print("F{} = {}".format(n, fib))
    
fibonacci(6)

Вывод:

 F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8

Ответ №2:

Вы можете использовать параметры по умолчанию, подобные этому:

 def fibonacci(n, a=1, b=1):
    if n==0:
        return;
    else:
        print(a)
        fibonaci(n-1, b, a b)

fibonacci(10)

Output:
1
1
2
3
5
8
13
21
34
55

Ответ №3:

Это возможно, но вам нужно иметь нелокальное значение, чтобы помнить, было ли число уже напечатано. Простой способ — использовать замыкание и локально определенную функцию:

 def fibonacci(n):
    done = -1
    def fibo(n):
        nonlocal done
        if n <= 1:
            fib = n
        else:
            fib = fibo(n-1)   fibo(n-2)
        if n > done:
            print("F{} = {}".format(n, fib))
            done = n
        return fib
    fibo(n)

Теперь вы можете сделать:

 >>> fibonacci(6)
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8

Ответ №4:

Вы можете сделать свою функцию генератором и использовать распаковку в инструкции печати (при необходимости с новым разделителем строк).:

 def fibo(n,a=0,b=1):
    yield a
    if n>1:
        yield from fibo(n-1,b,a b)

print(*fibo(10),sep="n")

0
1
1
2
3
5
8
13
21
34

Вы также можете использовать функцию print внутри функции, но теперь так должны работать функции:

 def fibo(n,a=0,b=1):
    print(a)
    if n>1:fibo(n-1,b,a b)

fibo(10)

Кстати, современная версия последовательности Фибоначчи начинается с нуля