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

Question

[Doaxan]

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

Comments

[Lynn «Кофеман»]

Вообще-то это неправда.

Результат сильно зависит от криворукости программиста.

[Adamos]

Это правда - но в определенном контексте.
В низкоуровневых языках математика работает быстро, а вызов функции сильно затратен. Поэтому в них разворачивание рекурсии в линию уменьшает оверхед.

Для высокоуровневых языков это может вовсе не иметь смысла.

Answer 1

[Mercury13]

Потому что этот алгоритм, будучи рализован в лоб без всяких кэшей и ускорителей, неоптимален! F(n–2) высчитывается дважды, F(n–3) трижды, F(n–4) пять раз, и т.д. по Фибоначчи.

Что читать, сказать не могу (в том издании Кормена, что у меня, маловато), гугли «динамическое программирование». Хотя поначалу поможет и Кормен.

ЗЫ. В некоторых случаях помогает вычисление в лоб, но с простеньким кэшем, который снизит повторяемость если не для всех входов, то хоть для самых вопиющих.

ЗЗЫ. Программисты не любят рекурсию по многим причинам. 1. Сложно наладить аварийный стоп. 2. Системный стек ограничен и есть риск переполнения.

Comments

[Кобальт Грозный]

тут поможет и tail recursion

[Mercury13]

Не поможет. 1. Она там не хвостовая. После рекурсии идёт операция +. 2. Хвостовая рекурсия не имеет ничего общего с кэшированием результатов, она только экономит стек. Порядок сложности остался тот же.

[SeptiM]

Mercury13: такую рекурсию можно сделать хвостовой: достаточно передавать в результат два последних числа вместо одного.

[Mercury13]

В принципе, да, но это уже преобразование, основанное на ассоциативности сложения.

Answer 2

[Mrrl]

Совсем не факт, что рекурсивные алгоритмы медленнее. Я только что написал тестовый пример - перебор чисел, все цифры в которых различны. Рекурсивная форма работает примерно на 10% быстрее, чем нерекурсивная, и на её написание ушло в несколько раз меньше времени.

Comments

[Doaxan]

Вы можете привести примеры конкретнее?

[Mrrl]

class Program {
        static int TestRec(int[] A,int L,int idx) {
            if(idx==L) return 1;
            int res=0;
            for(int a=0;a<10;a++) {
                bool q=false;
                for(int j=0;j<idx;j++) if(A[j]==a) {
                        q=true; break;
                    }
                if(q) continue;
                A[idx]=a;
                res+=TestRec(A,L,idx+1);
            }
            return res;
        }

        static int TestLin(int[] A,int L) {
            int res=0;
            int ptr=0;
            for(;;) {
                if(ptr==L) {
                    res++;
                    ptr--;
                } else A[ptr]=-1;
                for(;;) {
                    if(ptr<0) return res;
                    A[ptr]++;
                    if(A[ptr]==10) ptr--;
                    else {
                        bool q=false;
                        for(int j=0;j<ptr;j++) if(A[j]==A[ptr]) {
                                q=true; break;
                            }
                        if(!q) {
                            ptr++;
                            break;
                        }
                    }
                }
            }
        }




        static unsafe void Main(string[] args) {
            int[] A=new int[10];
            int res1=0,res2=0;
            DateTime t0=DateTime.Now;
            for(int u=0;u<10;u++) res1+=TestRec(A,10,0);
            DateTime t1=DateTime.Now;
            for(int u=0;u<10;u++) res2+=TestLin(A,10);
            DateTime t2=DateTime.Now;

            Console.WriteLine("TRec={0}, res={1}",t1-t0,res1);
            Console.WriteLine("TLin={0}, res={1}",t2-t1,res2);
        }

    }

Answer 3

[SeptiM]

Я вижу здесь два разных вопроса.

Первое -- можно сделать два рекурсивных алгоритма. Один запоминает результат и потому работает линейно, другой -- нет и работает экспоненциально. Я когда-то делал простенькую иллюстрацию на эту тему. Алгоритмы считают четырнадцатое число Фибоначчи. На эту тему я бы почитал Кормена в переводе Шеня.

Второй вопрос, если у нас есть два асимптотически одинаковых алгоритма (или нам так кажется). Например, линейный цикл против линейной рекурсии с запоминанием. Здесь никаких прямых ответов не получится. С одной стороны рекурсия кушает ресурсы на стек вызовов, с другой -- запоминание может существенно сократить вычислительные расходы + есть набор трюков, которые позволяют ускорить вычисления с обеих сторон.