Программа на си

[peregrine]

unimix, по результату (сферическому в вакууме) - да, а по логике работы - нет.

[.ubuntufan]

peregrine

И по результату и по логике - да.
В некоторых языках - Haskell, Erlang и т.д. рекурсия полностью заменяет циклы.

[peregrine]

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

[.ubuntufan]

Если только про C разговор то да. Если нет то

Хвостовая рекурсия это частный вид рекурсии, который оптимизируется компилятором до итерации.

Чем не цикл?

[Protopopulus]

Если только про C разговор то да. Если нет то
...
Чем не цикл?

Логикой работы:
Цикл:

Код: [Выделить]

movq $100, %rcx // i = 100;

begin:
cmpq $0,   %rcx // i == 0 ?
je   stop       // если итератор == 0, то завершить цикл
...
...             // тело цикла
...
subq $1,   %rcx // --i
jmp  begin      // к началу цикла

stop:
...             // инструкции программы

Рекурсия:

Код: [Выделить]

function:
push %rbp       // преамбула функции,
movq %rsp, %rbp // в которой запихивается
                // в стек 4 (х32) или 8 (х64) байта
...
...             // тело функции
...

jmp  function   // рекурсивный вызов

movq %rbp, %rsp // эпилогфункции,
pop  %rbp       // в котором извлекается из стека
                // 4-8 байт (см. выше).
                // Но из-за рекурсии, извлекается
                // только после завершения функции
ret             // банальный return в тело программы
Вроде бы, так записал. Давно ассемблером не занимался...

UPD: Многие компиляторы зачастую преобразуют рекурсивные функции, если могут, конечно, в циклы, дабы, в ходе выполнения, не кончился вдруг стек.

[.ubuntufan]

Protopopulus

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

http://it.kgsu.ru/Prolog/pro040.html

[Protopopulus]

.ubuntufan, ну ладно, не велика разница. Рекурсия - это рекурсия - это рекурсия - это рекурсия - это... А так-то да, по сути,  любая рекурсивная функция, в том числе и на Си, может быть представлена эквивалентной реализацией посредством цикла, т.е.:

Код: [Выделить]

begin:
cmp $1, %rcx // проверка флага завершения
je  stop
...
...          // тело цикла
...
mov $1, %rcx // установка флага завершения
...
jmp begin
stop:
...


[unimix]

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

Да и не всегда же цикл должен быть бесконечным.

[Delit]

А по моему изначальный код выглядит и читается проще чем код с циклом.

[Sly_tom_cat]

Delit, позволю принципиально не согласится:

Конструкция типа:

Код: [Выделить]

метка 1:
если <условие> то переход метка 2
...
...
переход метка 1
выглядит гораздо более громоздко чем

Код: [Выделить]

пока <условие> выполнять {
...
... }
... не говоря уже о том что заводятся дополнительные два идентификатора меток. В большом объеме кода - чем меньше идентификаторов тем меньше шансов в них запутаться. Именно поэтому есть много сторонников отказа от goto в языках программирования более высокого уровня чем ассемблер.

Многие, правда, возражают что тот же фортран ...... но забывают, что фортран, по сути, - макро-ассемблер.

[Sly_tom_cat]

unimix, вот зря вы тут рекурсию приплели.

Рекурсия сама по себе оправдана в очень узком круге задач (часто чисто академических). В прикладных задачах для рекурсии практически не сыскать применения ИМХО. А по ресурсоёмкости рекурсия вообще запредельная при реализации на языках высокого уровня . Не всегда оптимизатор кода может сделать приличную по потребляемым ресурсам рекурсию, а уж если язык интерпретируемый - то там и вообще все очень плохо...

[Delit]

Код: [Выделить]


метка 1:
...
...
если <условие> то переход метка 1


выглядит боле естественно чем

Код: [Выделить]

{
...
...
} пока <условие> выполнять
мне кажется что циклы не должны управлять логикой программы

[unimix]

Sly_tom_cat, прикладные задачи -- это какие? Вот если мне надо построить дерево из XML файла, или вывести иерархию репозитория, или пройтись по структуре файлов, то всегда выкручиваться простыми циклами со своими стеками?

Я конечно люблю делать сложные циклы, но иногда легче запустить рекурсивные функции или объекты, которые работают по тому же принципу.

[Sly_tom_cat]

Delit, в начальном коде был цикл while-do, а не описанный вами цикл do-until/do-while. Именно while-do-цикл требует два перехода (условный и безусловный), и именно он выглядит гораздо внятнее в цикловой записи, а не в goto-шной.

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


unimix, так я же не говорил никогда/нигде и т.п. крайности. Я сказал, что задачи прикладного плана редко требуют рекурсивных решений. Пример с XML - это один из тех случаев когда да - оно нужно.

[peregrine]

Protopopulus, далеко не любая рекурсия может быть представлена циклом (иногда может быть очень сложно, а то и невозможно).
Delit, когда кажется, креститься надо. Циклы рулят и педалят.