Есть вопрос про оптимизацию рекурсии на примере вычисления n-го числа

Question

Есть вопрос про оптимизацию рекурсии на примере вычисления n-го числа

Фибоначчи. Простой вариант, когда мы используем представление fib n = fib (n – 1) + fib (n – 2), работает очень долго даже на n = 100. В качестве решения предлагается использовать аккумулятор и считать с 0, например, fib n = helper 0 1 n, где в теле helper индекс n уменьшается до 0 с каждым шагом, мы как бы бежим из 0 к n числу, проводя расчет попутно двух чисел. Есть вариация с генератором по типу fib a b = a : b : fib b (a + b), которая работает тоже очень быстро. Какие есть еще идеи оптимизации выполнения рекурсивных функций?

#haskell #programming #russian

0

13.07.2022