Каким образом рассчитывается функция фибоначчи?

Question

[Александр]

Здравствуйте. Объясните, каким образом рассчитывается данная функция, какова последовательность?

function fibo($x){
	if ($x < 3) {
        return 1; 
    }else{
		return fibo($x-1) + fibo($x-2);
	};
};
	echo fibo(10);

Comments

[Lynn «Кофеман»]

Эээ, тут написано «в лоб» по опреденению последовательности Фибоначчи. Что может быть непонятного?

[Александр]

Алексей Тен: Не совсем была понятна последовательность сложения чисел.

[taurus90]

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

[Александр]

taurus90: не буду тебе мешать.

Answer 1

[Dmitry Demin]

Во-первых, ваш алгоритм не совсем корректен.

function Fibo(n) {
    if (n<2)
        return n;
    else
        return FIBO(n-1)+FIBO(n-2);
};

Во-вторых, в принципе, такой алгоритм является крайне медленным. Вот пример его стэка вызовов для пятого числа.

Если не вдаваться в подробности, то уже 50-е число такой алгоритм будет считать несколько минут.

Посему могу предложить использовать memoize подход (как в underscore)

var FIBO2=_.memoize(function(n) {{
    if (n<2)
        return n;
    else
        return FIBO2(n-1)+FIBO2(n-2);
});

либо воспользоваться итеративным алгоритмом

function FIBO3(n) {
    if (n<2) return n;
    var x=0,
        y=1,
        z;
    for (var i=1; i<n; i++) {
        z=x+y;
        x=y;
        y=z;
    }
    return z;
};

Итеративный алгоритм опережает остальные по скорости на несколько порядков при разовых вычислениях, однако memoize подход позволяет сэкономить на вычислениях при частом использовании функции (+за одно выполнение закэшируются результаты для всех n, стоящих перед требуемым).

Comments

[Котик Антон]

Во-первых, ваш алгоритм не совсем корректен

Fibo(0); // -1
Fibo(1); // 0
Fibo(2); // 1

[Lynn «Кофеман»]

Про корректность спорно. Зависит от точки отсчёта. У вас последовательность начинается с 0, 1, 1, у автора с 1, 1, 2.

[Lynn «Кофеман»]

Учитывая, что по легенде всё начиналось с пары кроликов, 0 там это уже более поздняя формализация

[Dmitry Demin]

27cm: алгоритм исправлен для отсчёта с 1-ой позиции (было лениво переделывать иллюстрацию).

[Dmitry Demin]

27cm: но я уже исправил обратно. Не дай боже кто-нибудь скопирует себе неверный алгоритм.

[Александр]

Dmitry Demin: что такое memoize?

[Dmitry Demin]

Александр: кэширование результата выполнения функции.

Answer 2

[Nikbes]

https://learn.javascript.ru/task/fibonacci-numbers

Answer 3

[GreatRash]

Можно вычислять чилсо Фибоначчи при помощи формулы Бине.

Answer 4

[Кирилл Пензин]

Рекурсивный подсчёт n-го числа в последовательности Фибоначчи.
Например:

#fibo(4)
#fibo(4)->fibo(3)+fibo(2)
#fibo(2)-> return 1
#fibo(3)-> fibo(2) + fibo(1)
#fibo(2)-> return 1
#fibo(1)-> return 1
#fibo(3)-> return 1+1
#fibo(4)-> return 2+1
#return 3