— Тема сегодняшнего урока: рекурсия, — препод обвёл взглядом группу. — Сегодня мы разберём её на примере ряда Фибоначчи.

Как известно, ряд Фибоначчи начинается с двух единиц, а каждый следующий член равен сумме двух предыдущих. То есть

a₁=1

a₂=1

a_n=a_n-1+a_n-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-ое число a_n-i+1 раз. То есть, например, при счёте 10-го числа мы считаем 9 и 10-е число 1 раз, 8-е 2 раза, 7-е 3 раза, 6-е 5 раз, 5-е 8 раз и т.д. При счёте 40-го числа мы обращаемся к 5-ому числу около 15 миллионов раз!

Заметим, что при вычислении a_n мы считаем a(n-2) два раза (непосредственно и считая a_n-1), поэтому мы можем смело утверждать, что

a_n=a_n-2×2+a_n-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 секунды

— Когда есть возможность не использовать рекурсию, не используйте, — сказал препод.