там упражнение,
там упражнение, то можете сравнить свой результат с приведенным в следующей таблице:
Стековая операция Содержимое стека после выполнения стековой операции
Рис. 1.
Push Fib(5)
Push Fib(5) Fib(3)
Push Fib(5) Fib(3) Fib(1)
Pop Fib(5) Fib(3)
Push Fib(5) Fib(3) Fib(2)
Pop Fib(5) Fib(3)
Pop Fib(5)
Push Fib(5) Fib(4)
Push Fib(5) Fib(4) Fib(2)
Pop Fib(5) Fib(4)
Push Fib(5) Fib(4) Fib(3)
Push Fib(5) Fib(4) Fib(3) Fib(1)
Pop Fib(5) Fib(4) Fib(3)
Push Fib(5) Fib(4) Fib(3) Fib(2)
Pop Fib(5) Fib(4) Fib(3)
Pop Fib(5) Fib(4)
Pop Fib(5)
Pop Пусто
Как видим, вызовы Fib с одинаковыми параметрами повторяются многократно; это ведет к дублированию вычислений и, соответственно, избыточному расходу времени run-time. Предлагаемый рисунок - т.н. фибоначчиево дерево - наглядно демонстрирует причину наших неудач: точки рекурсивных вызовов совпадают с узлами дерева, а одинаковых среди последних - немало.
Что ж, - повторимся, - если с рекурсией все обстоит так "плохо",
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
