— Тема сегодняшнего урока: рекурсия, — препод обвёл взглядом группу. — Сегодня мы разберём её на примере ряда Фибоначчи.
Как известно, ряд Фибоначчи начинается с двух единиц, а каждый следующий член равен сумме двух предыдущих. То есть
a1=1
a2=1
an=an-1+an-2
Поэтому нам было предложено написать функцию, которая считает число Фибоначчи таким вот рекурсивным образом:
integer(8) recursive function a(n) result (r)
integer(8) :: n
intent(in) :: n
if (n > 2) then
r = a(n-1) + a(n-2)
else
r = 1
end if
return
end function a
Видно, что мы считаем тут одно и то же сто тыщ миллионов раз. При счёте n-ного числа ряда мы считаем i-ое число an-i+1 раз. То есть, например, при счёте 10-го числа мы считаем 9 и 10-е число 1 раз, 8-е 2 раза, 7-е 3 раза, 6-е 5 раз, 5-е 8 раз и т.д. При счёте 40-го числа мы обращаемся к 5-ому числу около 15 миллионов раз!
Заметим, что при вычислении an мы считаем a(n-2) два раза (непосредственно и считая an-1), поэтому мы можем смело утверждать, что
an=an-2×2+an-3
Что ж, напишем и такую функцию:
integer(8) recursive function b(n) result (r)
integer(8) :: n
intent(in) :: n
if (n > 2) then
r = b(n-2)*2 + b(n-3)
else if (n > 0) then
r = 1
else
r = 0
end if
return
end function b
Здесь при расчёте 40-го числа мы посчитали 5-е всего лишь 8 тысяч раз. И наконец нам, ура-ура, предложили написать функцию без использования рекурсии, где каждое число мы считаем по одному разу:
integer(8) function c(n)
integer(8) :: n,i,x=0,y=1,z=1
intent(in) :: n
do, i=1, n-1
z = x + y
x = y
y = z
end do
c = y
return
end function c
Вот такие три функции мы написали. Понятно, что при расчёте даже 10-го числа разница в скорости незаметна, однако, например, при 50-ом числе мы можем наблюдать интересный результат (на моём компьютере, скомпилировано без оптимизации):
1 алгоритм: 77,21 секунды
2 алгоритм: 0,0056 секунды
3 алгоритм: 0,000001 секунды
— Когда есть возможность не использовать рекурсию, не используйте, — сказал препод.