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

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

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

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

5
задан TMS 8 August 2011 в 17:57
поделиться