Почему рекурсивные алгоритмы работают медленнее своих линейных аналогов?

#алгоритм #циклы #рекурсия

Не буду приводить пример кода, достаточно вспомнить вычисление n-го члена ряда Фибоначчи:
F(n) = F(n-1) + F(n-2). И что стоит прочитать, чтобы знать ответ на подобные вопросы?
    

Ответы

Ответ 1

Cтоимость вызова функции в языках, которые поддерживают tail call optimization (например,
любой язык платформы .net - C#, F#, C++ CLI) практически не отличается от обычного
цикла. И даже если эту оптимизацию применить нельзя - вызов невиртуальной функции обычно
достаточно дешев.

Поэтому рекурсивные алгоритмы работают с той же скоростью, что и их линейные аналоги.
Если "аналоги" употребляется в прямом смысле, то рекурсия - это способ организации кода.

Конкретно в случае Fib вы обычно реализуете два различных алгоритма:


в линейном вы высчитываете значения членов последовательности один раз.
в рекурсивном вы скорее всего высчитываете F(какого-то конкретного x) несколько раз.


Это расхождение убирается использованием техники под названием мемоизация (memoization)
- кэшированием результатов вызова F(x). Т.к. Fib - это чистая функция (она зависит
только от своих аргументов), то результат ее выполнения легко кэшируется:

вот вариант который будет каждый раз вычислять значение Fib (x) - медленный

let rec fibs n = 
  if n < 1 then 1 else
  (fibs (n - 1)) + (fibs (n - 2)) 


вот вариант, который будет вычислять значение Fib (x) всего один раз для каждого x:

let rec fibs = memoize (fun n ->
  if n < 1 then 1 else
  (fibs (n - 1)) + (fibs (n - 2)))


где memoize это:

open System.Collections.Generic

/// The function creates a function that calls the argument 'f'
/// only once and stores the result in a mutable dictionary (cache)
/// Repeated calls to the resulting function return cached values.
let memoize f =    
  // Create (mutable) cache that is used for storing results of 
  // for function arguments that were already calculated.
  let cache = new Dictionary<_, _>()
  (fun x ->
      // The returned function first performs a cache lookup
      let succ, v = cache.TryGetValue(x)
      if succ then v else 
        // If value was not found, calculate & cache it
        let v = f(x) 
        cache.Add(x, v)
        v)


Кстати, Fib - это настолько типичный пример для мемоизации, что именно он показан
в вики хаскеля в разделе Memoization with recursion, причем реализация мемоизации там
в разы короче, чем на F#:

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)




Как напомнил ВОРОН, не любую рекурсию можно оптимизировать через tail call. Например,
решение fibs на F# выше не подлежит такой оптимизации. Решение и поддержкой такой оптимизации
выглядит так:

let fib n =
    let rec loop acc1 acc2 = function
        | n when n = 0I -> acc1
        | n -> loop acc2 (acc1 + acc2) (n - 1I)
    loop 0I 1I n


По сути, это тот же цикл - функция, которая вызывает сама себя n раз, передавая себе
же два последних члена последовательности - но записанный в рекурсивной форме. Примерно
так внутри реализован Seq.unfold, позволяющий генерировать последовательности, в который
следующий элемент зависит от предыдущих.


Ответ 2

Вы неверно сравниваете. Вы должны сравнивать итеративный алгоритм с аналогичным рекурсивным:

(Fib(1), Fib(0)) = (1, 1)
(Fib(n+1), Fib(n)) = (Fib(n) + Fib(n-1), Fib(n))


который приводит к коду

(int, int) CalcFibHelper(int fcurr, int fprev, int n)
{
    if (n == 0) return (fcurr, fprev);
    return CalcFib(fcurr + fprev, fcurr, n-1);
}

int CalcFib(int n)
{
    (int result, int prev) = CalcFibHelper(1, 1, n);
    return result;
}




Компилятор, который хорошо умеет работать с хвостовой рекурсией, может преобразовать
рекурсивный код в итеративный. Предпочтение и скорость тех или иных реализаций алгоритма
зависит от компилятора: F#, например, лучше умеет работать с рекурсивными алгоритмами,
а C# — с итеративными.