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

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

Ответ

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, позволяющий генерировать последовательности, в который следующий элемент зависит от предыдущих.