Легко понять последовательность Фибоначчи, глядя на картинку

предисловие

Запущена новая серия «Глядя на картинки, чтобы легко понять структуры данных и алгоритмы», в основном с использованием изображений для описания общих структур данных и алгоритмов, которые легко читать и понимать. В эту серию входят десятки куч, очередей, списков, деревьев, графов, сортировки и так далее.

Фибоначчи

Фибоначчи (Леонардо Пизано, Фибоначчи, Леонардо Биголло, 1175-1250), также известный как Леонардо, был средневековым итальянским математиком. Он был первым на Западе, кто изучил последовательность Фибоначчи и представил Европе современную систему записи разрядных значений для написанных чисел и множителей. К основным работам относятся «Книга расчетов», «Геометрическая практика», «Книга квадратных чисел» и так далее.

Последовательность Фибоначчи

Последовательность Фибоначчи, также известная как последовательность золотого сечения или последовательность кролика, последовательность 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ..., вы можете видеть, что ее природа прежняя. сумма двух элементов равна последнему элементу.

проблема с кроликом

Последовательность Фибоначчи может быть использована для описания проблемы размножения кроликов.Вообще говоря, кролики становятся плодовитыми после двухмесячного рождения, и пара кроликов может рожать пару кроликов каждый месяц. Если не все кролики умрут, сколько пар кроликов можно будет вывести через год? Фактические результаты таковы, первый месяц и второй месяц у кроликов нет репродуктивной способности, поэтому есть только одна пара. Первая пара родилась на третьем месяце, всего получилось 2 пары. Четвертый месячный кролик продолжал рожать пару, а другая пара еще не была репродуктивной, всего было 3 пары. По аналогии количество кроличьих логарифмов от пятого месяца до двенадцатого месяца соответствует следующим образом.


месяцы	1	2	3	4	5	6	7	8	9	10	11	12
логарифм	1	1	2	3	5	8	13	21	34	55	89	144

выражение

f(x) = \left\{\begin{matrix} 0,& &x=0 \\ 1,& &x=1 \\ f(x-1)+f(x-2),& &x>=2,x \in N^* \end{matrix}\right.

рекурсивная реализация

int fib(int n){
    if (n == 0)
       return 0;
    if (n == 1)
       return 1;
    return fib(n - 1) + fib(n - 2);
}

Если n=4, посмотрите на стек рекурсивного процесса.

① Вызовите функцию fib и передайте значение параметра 4.

② fib(4)=fib(3)+fib(2), вам нужно продолжать вызывать fib(3), а fib(2) не входит в стек выполнения первым.

③ fib(3)=fib(2)+fib(1), вам нужно продолжать вызывать fib(2), fib(1) не входит в стек выполнения первым.

4 FIB(2)=FIB(1)+FIB(0), необходимо продолжить вызов FIB(1), FIB(0) не входит в стек выполнения.

⑤ fib(1) возвращает 1, прекращает коллировать вниз, а затем fib(0) на предыдущем шаге входит в стек.

fib(0) возвращает 0, тогда fib(2)=fib(1)+fib(0)=1 в ④

Затем стек возвращается к ③, потому что fib(3)=fib(2)+fib(1), поэтому поместите fib(1) в стек.

fib(1) возвращает 1, тогда fib(3)=fib(2)+fib(1)=1+1=2 в ③.

Затем стек возвращается к ②, и, поскольку fib(4)=fib(3)+fib(2), fib(2) помещается в стек. И fib(2)=fib(1)+fib(0), поэтому fib(1) помещается в стек. В этот момент fib(1) напрямую возвращает 1, а затем продолжает помещать fib(0) в стек. Тогда fib(2)=fib(1)+fib(0)=1 и, наконец, fib(4)=fib(3)+fib(2)=3.