Соотношение листьев к общему количеству узлов в стеке вызовов Фибоначчи

Question

Если вы посмотрите на рекурсивную реализацию вычисления n-го числа Фибоначчи (корень 100, дети 99 и 98, внуки 98, 97, 97 и 96 и т. Д. И т. Д.), Примерно, каково будет соотношениеколичество листьев к общему количеству узлов в рекурсивном дереве?

    100
   /   \
  98   97
 /  \   .
96  97  .
.    .  .
.    .  

Не домашнее задание, просто академически любопытно по этому поводу.(И да, я понимаю, что рекурсивная реализация - ужасный способ вычисления чисел Фибоначчи)

Answer 1

Количество листьев просто F(n), поскольку F(i) - это просто количество листьев под этим узлом. Вы понимаете почему? (подсказка: используйте индукцию)

Количество неконечных узлов - это количество листовых узлов-1. Это свойство двоичных деревьев. Таким образом, общее количество узлов составляет F(n) + F(n)-1 = 2F(n)-1.

Соотношение, таким образом, приближается к 1/2 с ростом n.

Answer 2

fib (x) состоит из листьев fib (x-1) и листьев fib (x-2).Таким образом, вы получаете то же рекурсивное уравнение, что и для чисел Фибоначчи.

Если точкой завершения (листья) являются Fib1 и Fib0, то

tree   numofleaves
fib2   2
fib3   3
fib4   5
fib5   8
fib6   13
...

и numofleaves (x) = fib (x + 1).

Для числа узлов вы получите уравнение numnodes (x) = 1 + numnodes (x-1) + numnodes (x-2).

Answer 3

Я фактически по индукции разработал доказательство, которое показывает, что число листьев в дереве Фибоначчи всегда превышает число внутренних узлов.

Доказательство: пусть E (n) - количество листьев дерева Фибоначчи для ввода n, и M (n) - число внутренних узлов дерева Фибоначчи для ввода n

   E(n) >= M(n) + 1

Базовые случаи:

f (0): E (0) = 1, M (0) = 0

f (1): E (1) = 1, M (1) = 1

f (2): E (2) = 2, M (2) = 1

f (3): E (3) = 3, M (3) = 2

Листья дерева размером n равны листьям каждого поддерева:

E (n) = E (n - 1) + E (n - 2)

Внутренние узлы дерева размера n равны внутренним узлам каждого поддерево, плюс корень

M (n) = M (n - 1) + M (n - 2) + 1

E (n)> = [M (n - 1) + 1] + [M (n - 2) + 1] (по индуктивной гипотезе)

Итак, E (n) = M (n - 1) + M (n - 2) + 2

Итак, E (n)> = M (n) + 1, QED