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

[unimix]

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

[Sly_tom_cat]

unimix, вот поэтому я и говорил - не стоит изначально к разговору о циклах примешивать рекурсивность.... не стоит переусложнять простой вопрос.

[Protopopulus]

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

Примеры можно?

[Sly_tom_cat]

Protopopulus, обход произвольного дерева.

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

[Protopopulus]

обход произвольного дерева.

Так и думал, что не будет достойного примера (не в обиду). Лично столкнулся один раз - делал дерево поиска (на чистом Си), в неблагоприятных случаях, программа падала с кончавшимся стеком. Да, данных было много, порядка 140 МиБ пар флоатов (координаты). После чего, переписал на условный цикл. Ничуть не сложнее. По-другому, но не сложнее. Просто добавляется FILO для точек возврата из ветви.

[peregrine]

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

[Sly_tom_cat]

Рекурсия бъет цикл наглядностью кода. Ресурсоемкостью - проигрывает однозначно.

[Protopopulus]

peregrine, Sly_tom_cat, я за всю свою практику так и не нашел алгоритма, реализуемого исключительно рекурсивно. Всегда (в моей практике) можно написать эквивалент на условном цикле. Просто это уже профессиональный интерес - найти исключительно рекурсивный алгоритм, применимый в практических целях.

Да и про наглядность не согласен. Типовой факториал...
Рекурсивно:

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

int f(int x) {
    if(x == 0) {
        return 1;
    } else {
        return x * factorial(x - 1);
    }
}
Циклом:

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

int f(int x) {
    int r = 1;

    while(x > 1) {
        r *= x;
        x--;
    }

    return r;
}


[Sly_tom_cat]

Protopopulus, дерево обойти (хотябы бинарное) тоже нагляднее циклом?

[Protopopulus]

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

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

[peregrine]

Protopopulus, обойти можно циклом всегда, ЕМНИП, даже теорема такая есть, другое дело, что это может быть очень и очень трудно, что может сделать задачу нерешаемой за разумные сроки.

[unimix]

В ООП чаще можно встретить рекурсию. Например, для обработки некоего события в дереве объектов, унаследованных от одного класса. А там наследование, инкапсуляция, полиморфизм...

[peregrine]

unimix, ага, в ООП больше ленятся писать код, но неоправданной рекурсии быть не должно нигде.

[alsoijw]

Рекурсия это не goto в программе на япе высокого уровня...

[Protopopulus]

Рекурсия это не goto в программе на япе высокого уровня...

Ага, это call или jmp в машинных инструкциях (читай goto).