|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 08 Mar 2002 21:51:51
To : Dmitry Demchuk
Subject : Re: Hерекурсивный алгоритм обхода дерева папок на диске
--------------------------------------------------------------------------------
Dmitry Demchuk wrote:
> ...
> >> Я всегда считал рекурсивным алгоритм, который вызывает сам себя
> >> и на каждом уровне расчитывая новые параметры вызова. ...
> AT> А что такое по-твоему "алгоритм вызывает сам себя"?
>
> Ка это что? Вызов алгоритма из его же тела. Как это еще можно понять?
А что такое "тело" алгоритма и что такое для алгоритма "вызов из тела".
Ты, видимо, говоришь не об алгоритме, а о _записи_ (реализации)
алгоритма. Hе надо путать _алгоритм_ и _реализацию_ _алгоритма_. Это
сильно разные вещи.
А рекурсия, как она встречается в программе на языке программирования
(функция вызывает саму себя и т.п.), это совершенно отдельное понятие -
синтаксическая рекурсия, рекурсивная реализация. К рекурсивности
алгоритма рекурсивность реализации абсолютно никакого отношения не
имеет. Для любого рекурсивного алгоритма существует циклическая
реализация. Для любого циклического алгоритма существует рекурсивная
реализация.
> AT> Hакопление
> AT> отложенных заданий в очереди (стеке или еще чем-то подобном) с
> AT> последующим примененем к ним того же алгоритма - это и есть вызов
> AT> самого себя, который мы в данном случае и наблюдаем.
>
> Именно в стеке. И именно параметров вызова. Создание очереди любым другим
> способом с последующей ее обработкой не есть признак рекурсии.
Есть разные типы терминологии. Да, иногда под рекурсией понимают именно
стековую рекурсию, из-за особого порядка отработки вызовов алгоритма и
наличия так называемого 'обратного хода' рекурсии (если это существенно
для алгоритма). Hо иногда рекурсивные алгоритмы определяют шире.
Основная причина, по которой рекурсивные алгоритмы выделяют среди других
алгоритмов, и по которой часто встает задача поиска истинно циклического
алгоритма по данному рекрсивному, заключается именно в том, что
рекурсивные алгоритмы расходуют память на хранение отложенных задач. И,
что важно, объем этой памяти нельзя ограничить константой (т.е.
величиной, не зависящей от размера входа). Если такой расход памяти
непримелем, то необходимо найти истинно циклический алгоритм (если
возможно). Замена стека на очередь при этом никого не интерсует - это
совершенно ничего не меняет.
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: good enough (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
