Пожалуйста, объясните этот простой код:
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
Я запутался с последней строкой, особенно потому, что, например, если n = 5, то будут вызваны fibonacci (4) + fibonacci (3) и так далее, но я не понимаю, как этот алгоритм вычисляет значение по индексу 5 этим метод. Пожалуйста, объясните с большим количеством деталей!
Ответы:
В последовательности Фибоначчи каждый элемент является суммой двух предыдущих. Итак, вы написали рекурсивный алгоритм.
Так,
Теперь вы уже знаете
fibonacci(1)==1 and fibonacci(0) == 0
. Таким образом, вы можете впоследствии рассчитать другие значения.Сейчас,
И из последовательности Фибоначчи
0,1,1,2,3,5,8,13,21....
мы видим, что для5th element
последовательности Фибоначчи возвращается5
.Смотрите здесь для обучения рекурсии .
источник
Есть 2 проблемы с вашим кодом:
Код
fibonacci(n - 1) + fibonacci(n - 2)
очень неправильный.
Проблема в том, что он вызывает Фибоначчи не в 50 раз, а гораздо больше.
Сначала он называет Фибоначчи (49) + Фибоначчи (48),
затем Фибоначчи (48) + Фибоначчи (47) и Фибоначчи (47) + Фибоначчи (46)
Каждый раз, когда он становится Фибоначчи (n) хуже, поэтому сложность экспоненциальная.
Подход к нерекурсивному коду:
источник
2*fibonacci(n+1)-1
увеличивается, поэтому оно растет с той же сложностью, что и сами числаВ псевдокоде, где n = 5, имеет место следующее:
Это разбивается на:
Это разбивается на:
Это разбивается на:
Это разбивается на:
В результате: 5
Учитывая, что последовательность Фибоначчи равна 1 1 2 3 5 8 ... , 5-й элемент равен 5. Вы можете использовать ту же методологию, чтобы выяснить другие итерации.
источник
Иногда рекурсию трудно понять. Просто оцените это на небольшом листе бумаги:
Я не уверен, как Java на самом деле оценивает это, но результат будет таким же.
источник
Вы также можете упростить свою функцию следующим образом:
источник
Важно отметить, что этот алгоритм является экспоненциальным, поскольку он не хранит результат предыдущих вычисленных чисел. например, F (n-3) вызывается 3 раза.
Для более подробной информации обратитесь к алгоритму dasgupta глава 0.2
источник
Большинство ответов хороши и объясняют, как работает рекурсия в Фибоначчи.
Вот анализ трех методов, включая рекурсию:
Вот мой код для проверки всех трех:
Вот результаты:
Следовательно, мы видим, что памятование - лучшее время и для циклических совпадений.
Но рекурсия длится дольше, и, возможно, вам следует избегать в реальной жизни. Также, если вы используете рекурсию, убедитесь, что вы оптимизируете решение.
источник
Это лучшее видео, которое я нашел, которое полностью объясняет рекурсию и последовательность Фибоначчи в Java.
http://www.youtube.com/watch?v=dsmBRUCzS7k
Это его код последовательности, и его объяснение лучше, чем я когда-либо пытался его напечатать.
источник
Для рекурсивного решения Фибоначчи важно сохранить вывод меньших чисел Фибоначчи, извлекая при этом значение большего числа. Это называется «памятка».
Вот код, который использует запоминание меньших значений Фибоначчи при получении большего числа Фибоначчи . Этот код эффективен и не выполняет несколько запросов одной и той же функции.
источник
в последовательности Фибоначчи первые два элемента равны 0 и 1, каждый другой элемент является суммой двух предыдущих элементов. то есть:
0 1 1 2 3 5 8 ...
таким образом, 5-й элемент - это сумма 4-го и 3-го элементов.
источник
Майкл Гудрич и др. Предлагают действительно умный алгоритм в структурах данных и алгоритмах на Java для рекурсивного решения фибоначчи за линейное время, возвращая массив [fib (n), fib (n-1)].
Это дает fib (n) = fibGood (n) [0].
источник
Вот решение O (1):
Формула числа Фибоначчи Бине используется для реализации выше. Для больших входов
long
можно заменить наBigDecimal
.источник
Последовательность Фиббоначи - это последовательность, которая суммирует результат числа при добавлении к предыдущему результату, начинающемуся с 1.
Как только мы поймем, что такое Fibbonacci, мы можем начать разбивать код.
Первый if statment проверяет базовый случай, где цикл может разорваться. Оператор else if ниже делает то же самое, но его можно переписать так ...
Теперь, когда базовый случай установлен, мы должны понять стек вызовов. Ваш первый вызов «fibonacci» будет последним, который разрешит стек (последовательность вызовов), поскольку они разрешаются в обратном порядке, из которого они были вызваны. Сначала вызывается последний вызываемый метод, затем последний, вызываемый перед этим, и так далее ...
Таким образом, все вызовы выполняются в первую очередь, прежде чем что-либо «рассчитывается» с этими результатами. При вводе 8 мы ожидаем выход 21 (см. Таблицу выше).
Фибоначчи (n - 1) продолжают вызывать до тех пор, пока они не достигнут базового случая, затем Фибоначчи (n - 2) вызывают до тех пор, пока он не достигнет базового случая. Когда стек начнет суммировать результат в обратном порядке, результат будет примерно таким ...
Они продолжают пузыриться (разрешаться в обратном направлении) до тех пор, пока правильная сумма не будет возвращена первому вызову в стеке, и вот как вы получите свой ответ.
Сказав это, этот алгоритм очень неэффективен, потому что он вычисляет один и тот же результат для каждой ветви, на которую разбивается код. Гораздо лучший подход - это подход «снизу вверх», где не требуется Memoization (кэширование) или рекурсия (глубокий стек вызовов).
Вот так...
источник
Большинство предлагаемых здесь решений работают в O (2 ^ n) сложности. Пересчет идентичных узлов в рекурсивном дереве неэффективен и тратит впустую циклы ЦП.
Мы можем использовать памятку, чтобы заставить функцию Фибоначчи запускаться за время O (n)
Если мы пойдем по пути динамического программирования снизу вверх, приведенный ниже код достаточно прост для вычисления Фибоначчи:
источник
Почему этот ответ отличается
Любой другой ответ либо:
(в сторону: ни один из них на самом деле не эффективен; используйте формулу Бине для прямого вычисления n- го члена)
Хвост Рекурсивный Фиб
Вот рекурсивный подход, который позволяет избежать двухрекурсивного вызова, передавая как предыдущий, так и предыдущий ответ.
источник
Это базовая последовательность, которая отображает или получает вывод 1 1 2 3 5 8, это последовательность, в которой сумма предыдущего числа, текущее число будет отображаться следующим.
Попробуйте посмотреть ссылку ниже Java Рекурсивная последовательность Фибоначчи Учебник
Нажмите здесь, чтобы посмотреть Java Рекурсивное руководство по последовательности Фибоначчи для кормления ложкой
источник
Я думаю, что это простой способ:
источник
Ответ RanRag (принятый) будет работать нормально, но это не оптимизированное решение до тех пор, пока оно не будет запомнено, как объяснено в ответе Анила.
Для рекурсивного подхода, описанного ниже, вызовы методов
TestFibonacci
минимальныисточник
источник
Используя внутренний ConcurrentHashMap, который теоретически может позволить этой рекурсивной реализации правильно работать в многопоточной среде, я реализовал функцию fib, которая использует как BigInteger, так и Recursion. Требуется около 53 мс, чтобы вычислить первые 100 чисел FIB.
Тестовый код:
источник
Вот одна строка фебоначчи рекурсивная:
источник
Попробуй это
источник
Просто чтобы дополнить, если вы хотите иметь возможность рассчитывать большие числа, вы должны использовать BigInteger.
Итерационный пример.
источник
http://en.wikipedia.org/wiki/Fibonacci_number более подробно
Сделать это так просто, как нужно, не нужно использовать цикл while и другой цикл
источник
источник
Используйте
while
:Преимущество этого решения в том, что его легко читать и понимать, надеясь, что это поможет
источник
Последовательность Fibbonacci - это последовательность, которая суммирует результат числа, которое мы добавили к предыдущему результату, мы должны начать с 1. Я пытался найти решение на основе алгоритма, поэтому я строю рекурсивный код, заметил, что я сохраняю предыдущий номер, и я изменил позицию. Я ищу последовательность Фиббоначи от 1 до 15.
источник
источник
Простые Фибоначчи
источник
@chro находится на месте, но он / она не показывает правильный способ сделать это рекурсивно. Вот решение:
источник