Блог

Я хочу написать рекурсивную функцию на Python для Фибоначчи.

x будет начальной точкой, y будет последующей x и l будет длиной.

Я не понимаю, в чем моя ошибка в мышлении:

  def fib(x, y, l, fibList=None):
    fibList = []
    z = x   y
    x = y
    fibList.append(z)
    y = z

    if len(fibList) <= l:
        return fib(x, y, l, fibList)
    else:
        return(fibList)
  

Результат:

 RecursionError: maximum recursion depth exceeded while calling a Python object
  

Я могу решить это с помощью цикла for, но не с помощью рекурсивной функции.

Здесь есть несколько проблем. Как только вы исправите бесконечную рекурсию, у вас все еще будет проблема.

Как указывает @Raqha, вам не нужно инициализировать свой список при каждом вызове fib функции, а только в первый раз, когда fibList параметр не указан и поэтому по умолчанию None используется значение .

Ваш код не может сгенерировать первые два числа в последовательности, 0 и 1 . Вы можете исправить это, просто инициализировав свой список, включив в него эти термины, и скорректировав логику, чтобы предоставить только N-2 дополнительных термина.

Сигнатура вашей функции может быть улучшена, чтобы вызывающей стороне было намного проще ее использовать. Вызывающий абонент заботится только о количестве терминов, которые он / она хочет. Пользователю не нужно знать, что вводить для начальных x значений и y значений.

Вот версия вашего кода с исправлением бесконечной рекурсии, исправлением недостающих терминов, а также с измененной подписью, чтобы пользователь мог вызывать функцию просто и очевидно:

 def fib(l, x=0, y=1, fibList=None):
    if fibList is None:
        fibList = [0, 1]
    z = x   y
    x = y
    fibList.append(z)
    y = z

    if len(fibList) < l-1:
        return fib(l, x, y, fibList)
    else:
        return(fibList)

print(fib(10))
  

Результат:

 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
  

Во второй строке, которую вы задаете fibList = [] . Это означает, что каждый раз, когда вы вызываете функцию рекурсивно, она сбрасывает список пустым, поэтому len(fibList) всегда будет равно 1.

Удалите эту строку, чтобы переменная fibList не сбрасывалась, тогда она должна правильно соответствовать вашему условию выхода. Как это написано, теперь оно работает вечно, пока не сломается.

В начале каждого fib вызова функции вы очищаете свой fibList with fibList = [] . Таким образом, длина списка всегда будет <= 1 равна, поэтому вы сталкиваетесь с бесконечным циклом рекурсии, что не очень хорошо. Вам нужно добавить что-то вроде if fibList is None:

При первом вызове функции «fib» без предоставления какого-либо 4-го оператора в списке аргументов, значение fibList изначально будет равно «None». Но позже, когда вы снова рекурсивно вызываете функцию «fib», вы предоставляете список fibList в списке аргументов. Таким образом, значение больше не равно «None». Поэтому при добавлении оператора if, как упоминалось выше, функция знает, когда вы вызываете функцию извне (когда вы вызываете ее в своем коде как «fib (1,2,10)»), или когда функция рекурсивно вызывает саму себя. И поэтому вы не сбрасываете список файлов каждый раз, когда вызываете функцию, а устанавливаете его только 1 раз в начале.

 def fib(x, y, l, fibList=None):
    if fibList is None:
        fibList = []
    z = x   y
    ...