адача 6. Составить рекурсивную программу-функцию вычисления n-го числа Фибоначчи, исходя из рекуррентного определения этих чисел:

                                          (1)

Решение. Наличие рекуррентного соотношения вида (1) сразу же определяет и базу рекурсии, и способ декомпозиции. Программа-функция fib(n) написана строго в соответствии с этим определением:

Контрольные примеры:

fib(1) = 1,              fib(5) = 8,               fib(10) = 89.

Функция fib(n) вряд ли подходит для вычисления чисел Фибоначчи при больших n. И происходит это потому, что в данном случае с ростом n дерево рекурсивных вызовов очень быстро разрастается. При этом многократно вычисляются значения функции в одних и тех же точках. На рисунке 5 стрелками представлена схема рекурсивных вызовов для fib(5) (имя функции обозначено через f).

Ускорение вычислений можно достигнуть разными путями. Например, используя вспомогательную рекурсивную функцию fibo(n,a,b) и обращение к ней с параметрами a=b=1:

Докажем, что так определенная функция fib(n) действительно вычисляет n-й член f(n) (n=0,1,2…) последовательности Фибоначчи. При n=0 имеем:

Далее, декомпозиция при рекурсивных вызовах проводится в соответствии со следующей схемой:

Но, в силу выбранной базы рекурсии, последнее выражение равно f(n), то есть fib(n)=f(n), что и требовалось доказать.

Заметим: вычисления по функции fibo(n,a,b) реализуются ровно за n рекурсивных обращений.

Рис. 5. Схематическое изображение рекурсивных вызовов при нахождении f(5).

Еще более эффективный способ вычисления f(n) получается с использованием матриц. Если

то

Это приводит к следующей рекурсивной программе-функции:

Отметим, что теперь количество рекурсивных вызовов для fiboo(n) имеет порядок, равный log₂(n), и, скажем, fiboo(200) в символьной форме вычисляется практически мгновенно.

Контрольные примеры: