Итеративное vs. Рекурсивное решение

[StopCry]

вот у меня есть 2 решения простенькой задачи:
(просто проверяет принадлежность элемента стеку)
Вот рекурсивное:

Используется синтаксис C

int find(duck * p, char x)
{
        int answer;
        if (pust(p) == 1)
                return 0;
        else
        {
                if (p->el == x)
                        return 1;
                else
                {
                        p = out(p);
                        answer = find(p,x);
                }
        }
}

Вот итеративное:

Используется синтаксис C

int find(duck * p, char x)
{
        if(pust(p) == 1)
                return 0;
        else
                if(p->el == x)
                        return 1;
                else
                        while(p->next != NULL && p->el != x)
                                p = p->next;
        if(p->el == x)
                return 1;
        else
                return 0;
}

Собственно вопрос: какое из них будет более оптимальным?
если нужно, то могу полный код предоставить.

[Xaositect]

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

[venco]

Итерация практически всегда эффективнее рекурсии. Даже если алгоритм требует множественной рекурсии, которую трудно реализовать итеративно, имеет смысл хотя бы часть рекурсии перевести в итерацию.
Кстати, при некоторых условиях современные компиляторы могут соптимизировать рекурсивный вызов в итерацию автоматически.
Если в вашем первом коде вставить правильный оператор return, то ваша рекурсия может быть соптимизирована.

[StopCry]

Прога в 2х файлах написана, так что вот файл, который в обоих вариантах неизменный:

Используется синтаксис C

void main()
{
        duck *p = NULL;
        f1 = fopen("input.txt","r");
        char c;
        fscanf(f1,"%c",&c);
        while(c !='.')
        {
                p = add(p,c);
                fscanf(f1,"%c",&c);
        }
        fclose(f1);
        f1 = fopen("char.txt","r");
        char x = inX(f1);
        int answer = find(p,x);
        f1 = fopen("output.txt","w");
        fprintf(f1,"%d",find(p,x));
        fclose(f1);
}

вот с итеративным:

Используется синтаксис C

#include <stdio.h>
FILE *f1;

struct duck{
        char el;
        duck *next;};

int pust(duck* p)//проверка на пустоту
{
  if (p == NULL)
      return 1;
  else
      return 0;
}

duck *clean (duck *p)//создание/очищение стека
{
        p = NULL;
        return p;
}
duck *add(duck *p, char x)
{
        if (pust(p) == 1)
        {
                p = new duck;
                p->el = x;
                p->next = NULL;
                return p;
        }
        else
        {
        duck *s;//s and p = first elem
        s = new duck;
        s->el = x;
        s->next = p;
        return s;
        }
}

char inX(FILE *f1)
{
        int c;
        fscanf(f1,"%c",&c);
        return c;
}

duck *out (duck *p)
{
        if(pust(p) == 0)
        {
                duck *s = p;
                p = p->next;
                s->next = NULL;
                return p;
        }
}

int find(duck * p, char x)
{
        int answer;
        if (pust(p) == 1)
                return 0;
        else
        {
                if (p->el == x)
                        return 1;
                else
                {
                        p = out(p);
                        answer = find(p,x);
                }
        }
}

а вот с рекурсивным:

Используется синтаксис C

#include <stdio.h>
FILE *f1;

struct duck{
        char el;
        duck *next;};

int pust(duck* p)//проверка на пустоту
{
  if (p == NULL)
      return 1;
  else
      return 0;
}

duck *clean (duck *p)//создание/очищение стека
{
        p = NULL;
        return p;
}
duck *add(duck *p, char x)
{
        if (pust(p) == 1)
        {
                p = new duck;
                p->el = x;
                p->next = NULL;
                return p;
        }
        else
        {
        duck *s;//s and p = first elem
        s = new duck;
        s->el = x;
        s->next = p;
        return s;
        }
}

char inX(FILE *f1)
{
        int c;
        fscanf(f1,"%c",&c);
        return c;
}

duck *out (duck *p)
{
        if(pust(p) == 0)
        {
                duck *s = p;
                p = p->next;
                s->next = NULL;
                return p;
        }
}

int find(duck * p, char x)
{
        int answer;
        if (pust(p) == 1)
                return 0;
        else
        {
                if (p->el == x)
                        return 1;
                else
                {
                        p = out(p);
                        answer = find(p,x);
                }
        }
}

[Esp_]

venco в сообщении #698349 писал(а):

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

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

[allchemist]

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

И все же рекурсия может быть очень полезной штукой, особенно при написании прототипа, или если рекурсивный вызов находится подальше от узких мест кода (принцип бутылочного горлышка).

-- Пн апр 08, 2013 10:20:44 --

Esp_ в сообщении #702916 писал(а):

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

Довольно сомнительное утверждение. Пример в студию!

[Pavia]

Жалко что на форуме нет ни одного теоретика из этой области.

Мысли в слух.
Определения рекурсии. Алгоритм в котором функция вызывающая сама себя принадлежит к классу рекурсивных. В том числе если функция вызывает сама себя через посредников.
Итерационный алгоритм алгоритм реализованный через цикл.

1) Любая рекурсивная функция может быть заменена итерационным алгоритмом с использованием стека.
2)Что касается хвостовой рекурсии, то она легко заменяется итерационным алгоритмом с константным значением памяти.
Что касается скорости, то не обязательно вторая реализация выигрывает у первой. К примеру за счёт отсечения первая может выигрывать. К примеру задача о 8 ферзях.

Esp_ в сообщении #702916 писал(а):

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

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

[venco]

Pavia в сообщении #707490 писал(а):

К примеру за счёт отсечения первая может выигрывать.

А что заставляет вас убирать отсечения из итеративного решения?

[Pavia]

venco в сообщении #707495 писал(а):

К примеру за счёт отсечения первая может выигрывать.А что заставляет вас убирать отсечения из итеративного решения?

Читайте внимательно и первый и второй итерационные. Что касается что не даёт во втором случае делать отсечения? То тут ответ прост ограничения на память о которых я написал выше. Т.е. по определению, мы не можем хранить предыдущие результаты, а значит вынуждены перевычислять их заново. Справедливости ради стоит заметить, что это относиться не ко всем классам задач.

[bin]

Pavia в сообщении #707490 писал(а):

Жалко что на форуме нет ни одного теоретика из этой области.

Ok! Давайте поговорим о теории

Для пояснения своей точки зрения на заданный вопрос начну с цитат из широко известных классиков:

Цитата:

“Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя.” Н. Вирт, Алгоритмы+структуры данных = программы, М.: Мир, 1985, С.151.
“Процедура является рекурсивной, если ее новая активация может начаться до того, как завершилась ее более ранняя активация” Ахо А., Сети Р., Ульман Дж., Компиляторы: принципы, технологии и инструменты. М.: Вильямс, 2003, C.378.
“Рекурсивные алгоритмы наиболее пригодны в случаях, когда поставленная задача или данные определены рекурсивно.” Н. Вирт, С. 153.
“Итак, вывод таков: следует избегать рекурсии, когда имеется очевидное итеративное решение поставленной задачи. Но это не значит, что всегда нужно избавляться от рекурсии любой ценой. […] Тот факт, что рекурсивные процедуры можно реализовать на не рекурсивных по сути машинах[bold -- bin], говорит о том, что для практических целей любую рекурсивную программу можно преобразовать в чисто итеративную. Но это требует явного манипулирования со стеком рекурсий, и эти операции до такой степени заслоняют суть программы, что понять ее становится очень трудно. Следовательно, алгоритмы, которые по своей природе скорее рекурсивны, чем итеративны, нужно представлять в виде рекурсивных процедур.” Н. Вирт, С. 155-156.

Продолжим практикой. Чтобы ознакомиться с конкретной всем известной реализацией в железе на Интеловских CPU до Pentium-4 включительно, можно прочитать и главу 15 учебника В.И. Юров, Assembler, 2-ое изд., СПб.: Питер, 2004. Там про процедуры и их реализацию на языке ассемблера. Сразу станет видно, что имел в виду Вирт, говоря о “не рекурсивных по сути машинах”. Если допустить незначительные упрощения, то можно сказать, что на уровне объектного кода, т.е. инструкций CPU, различия между рекурсией и итерацией сходят на нет – т.е. практически дело сводится к тому, доверяет программист компилятору составить список действий со стеком или же хочет сделать это собственноручно.

В процитированной выше книге Вирт не советует рекурсивно вычислять факториал. В заметке M.Trofimov, How Much Does a Recursion Cost? // J.of Pascal, Ada & Modula-2, Vol. 9, 1990, No. 3, p.6 я это сделал на IBM PC AT/MS DOS/Turbo Pascal 3.3 и сравнил по времени с итеративным решением – получилось не только не хуже, а даже чуть лучше. В уже сугубо научном журнале предложил оптимизацию (на рекурсивной процедуре) так называемого индекса Хосои (полное число паросочетаний молекулярного графа $+1$) – см. M.Trofimov, An Optimization of Procedure for Calculation of Hosoya's Index. // J of Mathematical Chemistry, 1991, No. 8, p. 327. А позже предложил эффективный алгоритм (рекурсивный с возвратом) для тестирования в СУБД молекулярных графов на изоморфизм: М.И. Трофимов, Е.А. Смоленский, Применение индексов электроотрицательности органических молекул в задачах химической информатики. // Известия РАН, сер.хим., 2005, №9, c. 2166. До сих пор получаю отзывы, но претензий к рекурсии еще не было Но может, у меня слишком особые задачи? Опять вернусь к классике. Вирт в своих книгах не только утверждал, что если структура данных рекурсивная, то и алгоритм, работающий с ней, удобнее делать рекурсивным, но и применил это на практике в компиляторах. И посмотрев классические компиляторы с открытым кодом, мы можем видеть, как эффективно они осуществляют грамматический разбор с применением рекурсии. При том, что рекурсия заменяется итерацией на уровне генерации объектного кода. И за Виртом пошли другие разработчики компиляторов…

Вывод простой: не заморачиваться без особых причин и не верить мифам, берущим исток с раннего фортрана и бейсика (где рекурсия не поддерживалась; не сравнивать с современным VBA!), а также не пытаться конкурировать с компилятором: современные компиляторы умеют работать со стеком гораздо лучше людей. Рекурсивный алгоритм и рекурсивная программа не хуже итеративных при прочих равных.

[iifat]

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