LINUX.ORG.RU

Рекурсия в питон и числа Фибоначчи

 ,


0

2

Привет.

Вот дано определение чисел Фибоначчи:

F(0)=0, F(1)=1, F(N)=F(N-1)+F(N-2).

Мне нужно написать функцию вычисления через рекурсию и цикл.

Вот я написала:


def f1(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

def f2(n):
    x, y = 0, 1
    if n == 0:
        return 0
    for i in range(n-1):
        x, y = y, x + y
    return y

Объясните пожалуйста,почему f1 с рекурсией работает в 10 млн. раз медленее чем f2. В гугле есть какая то фигня про рекурсию в питоне, но на английском языке и я не понимаю.

Потому что у тебя в первом случае переполняется стек рекурсивными вызовами. Либо пиши итеративно, как во втором примере, либо через хвостовую рекурсию.

LongLiveUbuntu ★★★★★ ()
Ответ на: комментарий от Lizhen

В любом случае там достаточно долгая раскрутка стека, даже при малых значениях входного параметра.

Смотри как делал я (писал на Scala, поправишь для Питона сам):

def fibbonacci(n: Int): Int = {
    @tailrec
    def runFibonacci(comp1: Int, comp2: Int, acc: Int, n: Int) : Int = n match {
      case 1 => acc
      case _ =>
        runFibonacci(comp1 = comp2, comp2 = comp1 + comp2, acc = comp1 + comp2, n - 1)
    }
    runFibonacci(0, 1, 1, n)
  }

LongLiveUbuntu ★★★★★ ()
Последнее исправление: LongLiveUbuntu (всего исправлений: 2)
Ответ на: комментарий от LongLiveUbuntu

5 звезд, а все как маленький.

Причем тут вообще стек? У него сложность алгоритма просто жуткая, потому что нет мемоизации, и кучу раз пересчитываются одни и теже числа

abs ★★★ ()

Lizhen

У тебя чтоб посчитать, например, fin(5) получится следующее

fib(5) = [fib(4)] + [fib(3)] // А теперь давай это раскрывать 
fib(5) = [fin(3) + fib(2)] + [fin(2) + fib(1)]
fib(5) = [fib(2) + fib(1) + fib(1) + fib(0)] + [fib(1) + fib(0) + 1] 

Я поставил квадратные скобки на первую операцию - чтоб проще было понимать где что раскрывается

Дальше раскрывать лень, как ты видишь тут кучу вычислений, и такие вещи как fib(2) встречались 3 раза, а такие как fib(1) 4 раза

abs ★★★ ()
Последнее исправление: abs (всего исправлений: 1)

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

anonymous ()
Ответ на: комментарий от LongLiveUbuntu

еще раз, причем тут рекурсия, стек, параметры и прочее?

рекурсивный алгоритм с мемоизацией будет работать примерно также быстро, а не в 10 миллионов раз (А именно об этом ТС и спрашивал, почему рекурсия НАСТОЛЬКО медленная)

А ответ на вопрос ТС - дело не в рекурсии, а в алгоритме. Рекурсия с мемоизацией даже если и будет медленнее то в разы, а не миллионы раз

abs ★★★ ()

Количество операций в обоих случаях несопоставимо. Математики даже изобрели специальную «нотацию O» для обозначения сложности, как оценку сверху количества операций с точностью до постоянного коэффициента.

Как было замечено выше, через рекурсию тоже можно эффективно записать.

dave ★★★★★ ()

сложность первого алгоритма - n-ое число Фибоначчи, то есть экспоненциальная.

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

def fib(n):
  if n == 0: return [0, 0]
  if n == 1: return [1, 0]
  ret = fib(n - 1)
  return [ret[0] + ret[1], ret[1]]
anonymous ()
Ответ на: комментарий от WitcherGeralt

В скале как видно из коробки тоже нет, хинтами/аннотациями подсказывают :)

А еще скалокод тут проиграл интертивному python в читаемости.

anonymous ()
Ответ на: комментарий от anonymous

В скале как видно из коробки тоже нет, хинтами/аннотациями подсказывают

Она там есть изкоробки. Аннотация нужна для проверки компилятором наличия хвостового вызова у функции.

LongLiveUbuntu ★★★★★ ()

https://www.youtube.com/watch?v=EdhN_gEDfUM

чтобы не перевычислять повтрно посчитанное, нужно хранить посчитанное в чем то (типа кэш) и проверять его перед вычислением нового числа фибо - если есть извлекать, иначе считать.
Может уже и сказали об этом
по моему у препода из ролика я видел объяснение про оптимальный алго вычисления чисел фибо через рекурсию, с обсуждением недостатков, но не на 100%.
всем же очевидно - зачем вычислять заново то, что уже вычислено. нужно только взять(вернуть) посчитанное.

Vlad-76 ★★★ ()

1. учебное заведение в котором рекурсию (начинают и ограничивают) объясняют через числа Фибоначчи - не топчик учебное заведение - и растрачивает(уч.зав) время обучаемых попусту.

2. Если стремитесь понять в чём польза рекурсии(т.е сильно-рекурсивных утверждений) то с.м https://ru.wikipedia.org/wiki/Функция_Аккермана

зы. https://ru.wikipedia.org/wiki/числа_Фибоначчи#Формула_Бине

anonymous ()
Ответ на: комментарий от LongLiveUbuntu

здесь(в уч.процессе) не нужно рекурентность второго порядка приплетать при объяснении рекурсии - ибо у личинок формируется превратное представление о рекурсии как о переусложнённой бне легкозаменимой форчиками и прочими мемоизациями - если вообще у личинок что-либо существенное формируется при таком ритуале

anonymous ()