Дерево-рекурсия Фибоначчи в структуре и интерпретации компьютерных программ

Question

В классическом тексте Абельсона / Суссмана Структура и интерпретация компьютерных программ , в Разделе 1.2.2 о рекурсии дерева и последовательности Фибоначчи, они показывают это изображение:

дерево-рекурсивный процесс, сгенерированный в вычислениях для 5-го числа Фибоначчи

Затем они пишут: «Обратите внимание, что все вычисления (fib 3) - почти половина работы - дублируются. На самом деле нетрудно показать, что число раз, которое процедура будет вычислять (fib 1) или (fib 0) (количество листьев в приведенном выше дереве в целом), точно равно Fib (n + 1) . "

Я понимаю, что они делают вывод о рекурсии дерева и о том, как этот классический случай рекурсии дерева Фибоначчи неэффективен, потому что рекурсивная функция вызывает себя дважды:

Древовидно-рекурсивная функция для вычисления числа Фибоначчи

Мой вопрос заключается в том, почему очевидно (то есть «не трудно показать»), что число листьев равно следующему числу Фибоначчи в последовательности? Я вижу визуально, что это так, но я не вижу связи с тем, почему число листьев (уменьшенные вычисления fib 1 и fib 0) должно быть индикатором для следующего числа Фибоначчи (в этомслучай 8, который представляет собой Fib 6, то есть 6-е число Фибоначчи, т.е. Fib n + 1 , где n равно 5).

Очевидно, как последовательность Фибоначчивычисляется - сумма двух предыдущих чисел в последовательности дает текущее число, но почему число листьев точно равно следующему числу в последовательности? Какая здесь связь (кроме очевидного, что если посмотреть на нее и сложить листы 1 и 0, то в этом случае, на самом деле, получается общее число 8, то есть следующее (6-е) число Фибоначчи, и такна)

Answer 1

«Нетрудно показать» сложнее, чем «очевидный».

Использовать индукцию с двумя базовыми случаями.
Давайте назовем число вычислений в Fib(x), Fib01(x).
Тогда

Fib01(0) = 1 by definition, which is Fib(1) 
Fib01(1) = 1 by definition, which is Fib(2)

Теперь предположим, что Fib01(k) = Fib(k+1) для k

Fib01(n) = Fib01(n-1) + Fib01(n-2) 
         = Fib(n) + Fib(n-1) 
         = Fib(n+1) by definition

КЭД.

Answer 2

Количество n = 1 предложений должно быть равно fib (n), потому что это единственное место, откуда берется ненулевое число, и если сумма некоторого числа 1s равна fib (n),их должно быть fib (n).

Поскольку fib (n + 1) = fib (n) + fib (n-1), нам просто нужно показать, что есть fib (n-1)оставляет вычисление fib (0). Для меня менее очевидно, как это показать, но, может быть, это индуктивно выпадает из предыдущего случая?

---

Возможно, более простой подход состоит в том, чтобы просто сделать все это индуктивно, тогда.

Для наших базовых случаев:

• N = 0: в дереве есть fib (N + 1) = fib (1) = 1 лист. Доказательство осмотром.
• N = 1: в дереве есть fib (N + 1) = fib (2) = 1 лист. Доказательство проверкой.

Шаг индукции: чтобы вычислить fib (N) для произвольного N, мы вычисляем fib (N-1) один раз и fib (N-2) один раз, и добавляем их результаты,По индукции в дереве есть листья fib (N), полученные в результате нашего вычисления fib (N-1), и листья fib (N-1) в дереве, полученные в результате нашего вычисления fib (N-2).

Таким образом, в нашем общем дереве есть листья fib (N) + fib (N-1), равные fib (N + 1). Что и требовалось доказать.