Дипломная работа: Рекурсия
Контрольные примеры.
Функция fib(n) вряд ли подходит для вычисления чисел Фибоначчи при больших n. И происходит это потому, что в данном случае с ростом n дерево рекурсивных вызовов очень быстро разрастается. На рис. 3.3 представлена схема рекурсивных вызовов для fib(5) (имя функции обозначено через f).
 |
Рис. 3.3. Схематическое изображение рекурсивных вызовов при
нахождении f(5)
Для ускорения вычислений можно было бы учесть, что
Это приводит к следующей рекурсивной программе функции:
Отметим, что теперь количество рекурсивных вызовов для fiboo(n) имеет порядок равный log2 (n) и, скажем, fiboo(200) в символьной форме вычисляется практически мгновенно.
Контрольные примеры.
fiboo(0)=1 fiboo(1)=1 fiboo(10)=89
fiboo(200) ® 453973694165307953197296969697410619233826
3.6 Алгоритм Ламберта вычисления e
Задача 7. Составить программу вычисления приближения к основанию натуральных логарифмов, то есть к числу е, используя следующий алгоритм Ламберта:
Решение. Указанный алгоритм предложен Ламбертом в 1766 году [6, с.70]. Организовать по нему рекурсивные вычисления труда не составляет. Здесь величины a(k) и b(k) задаются рекуррентными соотношениями, похожими на определение чисел Фибоначчи, но нелинейными. Однако это обстоятельство не привносит каких-либо дополнительных затруднений в программную реализацию соответствующих функций. Дело в том, что задание последовательности любыми рекуррентными соотношениями сразу решает проблему триады: осуществлена параметризация задачи, выделена база и задана декомпозиция.
Программа e(k) приближенно вычисляет e, обращаясь к рекурсивным функциям-подпрограммам a(k) и b(k):
