Один из классических рекурсивных алгоритмов, который вы увидите, предназначен для последовательности Фибоначчи. В этом сообщении в блоге я расскажу об итеративном решении.
Последовательность Фибоначчи — это последовательность чисел, в которой значение текущего числа равно значению двух предыдущих чисел, сложенных вместе. Примером может быть:
0, 1, 1, 2, 3, 5, 8, 13, 21...
В вопросе об алгоритме вам обычно задают что-то вроде «Дано число, верните значение этого индекса в последовательности». Таким образом, в приведенном выше примере, если заданное число равно 8, будет возвращено 21.
Давайте настроим нашу функцию с тем, что мы знаем:
function fibonacci(number){
}
Нам нужно будет создать нашу последовательность, так что вернитесь к предыдущему примеру:
0, 1, 1, 2, 3, 5, 8, 13, 21...
Мы знаем, что нам нужно начать с первых двух чисел, чтобы начать последовательность. Добавим это в нашу функцию:
function fibonacci(number){
let sequence = [0,1]
}
Также с этой настройкой массива мы знаем, что возвращаем индекс этого числа в последовательности:
function fibonacci(number){
let sequence = [0,1]
return sequence[number]
}
Теперь нам нужно добавить нашу логику для создания последовательности. Как и почти во всех других алгоритмах, мы начинаем с цикла for, только на этот раз мы настроим его немного по-другому. Вместо установки «i» равным «0». Мы собираемся установить его на «2». Это потому, что в нашей последовательности уже установлены индексы 0 и 1:
let sequence = [0,1]
Мы также собираемся настроить цикл так, чтобы он выполнялся только до тех пор, пока мы не достигнем заданного индекса последовательности, поэтому мы собираемся использовать оператор «≤»:
function fibonacci(number){
let sequence = [0, 1];
for (let i = 2; i <= number ; i++){
}
return sequence[number];
}
Теперь нам просто нужно добавить наши значения в последовательность. Мы знаем, что шаблон — это два предыдущих числа, которые являются значением следующего числа последовательности. Итак, давайте вставим эту логику в нашу функцию:
function fibonacci(number){
let sequence = [0, 1];
for (let i = 2; i <= number ; i++){
sequence.push(sequence[i - 2] + sequence[i -1])
}
return sequence[number];
}
Вот оно! Этот итеративный подход кажется достаточно простым, но рекурсивный выглядит еще проще:
function fibonacci(number) {
if (number < 2){
return number;
}
return fibonacci(number - 1) + fibonacci(number - 2)
}
Иногда самый чистый код не самый лучший. В терминах Big O наше итеративное решение будет выполняться быстрее с обозначением O (n), в то время как рекурсивное решение будет O (2 ^ n). Если бы мы запускали те же функции с 50 в качестве заданного индекса, мы могли бы увидеть это в действии. В результате наш итеративный подход выполняется намного быстрее, чем наш рекурсивный.
