РЕальная необходимость рекурсии

← →
TStas © (2006-03-18 16:33) [0]

ИМХО рекурсия реально нужжна лишь при обходе древовидных данных. НЕ обязательно дерева паппок или TTreeView, синатксического анализатора и проч. но именно в этом счучае. Кстати, и Фаронов высказал, хоть и не явно, паодобное мнение.
А для массивов я выработал для себя правило: если элемент массива используется не более одного раза, массив точно не нужен. Код, может, и не такой красивый, зато быстрее работает

← →
Sergey Masloff (2006-03-18 16:37) [1]

TStas © (18.03.06 16:33)
Доступ к элементу массива это очень незатратная операция. Практически бесплатная.

Рекурсия во многих случаях использоваться может. Как правило рекурсивное выражение очень компактно и легко читается код.

← →
TStas © (2006-03-18 16:40) [2]

Сабж был о НЕОБХОДИМОСТИ рекурсии. Кроме того, она ведь многократный вызов функции, т. е. должно тормозить, путь и не сильно.
Доступ к элементу массива, понятно, незатратный, но создание НЕНУЖНОГО массива...

← →
Kerk © (2006-03-18 16:43) [3]

Sergey Masloff (18.03.06 16:37) [1]

Рекурсию стоит заменять циклом, где это возможно. Рекурсия стек очень кушает.

← →
Sergey Masloff (2006-03-18 16:47) [4]

TStas © (18.03.06 16:40) [2]
Что в твоем понимании СОЗДАНИЕ массива. Подвинуть указатель стека?

А рекурсивный алгоритм конечно можно заменить на использование стека но читабельность...

← →
Sergey Masloff (2006-03-18 16:48) [5]

Kerk © (18.03.06 16:43) [3]
>Рекурсию стоит заменять циклом, где это возможно. Рекурсия стек очень >кушает.
Да это понятно. Только овчинка выделки стоит далеко не всегда. Впрчем есть разные области вполне вероятно что это может быть критичным.

← →
isasa © (2006-03-18 16:59) [6]

Да ну. Вычисление факториала рекурсивным методом очень симпатично получается!

← →
Nikolay M. © (2006-03-18 17:12) [7]

> isasa © (18.03.06 16:59) [6]
> Да ну. Вычисление факториала рекурсивным методом очень симпатично
> получается!

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

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

← →
TStas © (2006-03-18 17:41) [8]

Отлаживать ее очень противно. Я и спрашивал мнение участников о НЕОБХОДИМОСТИ. Т. е. Где не заменишь. Чтобы стек не кушала, поменьше локальных переменных или вообще - в отдельный модуль ее. Так Фаронов и делал. Тогда 8 байт

← →
Sergey Masloff (2006-03-18 17:50) [9]

TStas © (18.03.06 17:41) [8]
Ну если о НЕОБХОДИМОСТИ то ЛЮБУЮ рекурсию можно заменить на реализацию со стеком. "Концевые" рекурсии напрямую приводятся к циклам. Подробнее см. например Ахо, Хопкрофт, Ульман "Структуры данных и алгоритмы" Вильямс 2000 г. ISBN 5-8459-0122-7 глава 2.

← →
iZEN © (2006-03-18 17:53) [10]

Kerk © (18.03.06 16:43) [3], возможно стоит положиться не на системный стэк, а на программный. Например, обход дерева файловой системы с использование программного стэка:
public class DirectoryIterator implements Iterator<File> { private FastStack<File> _stack; private List<File> _next; public DirectoryIterator(File baseDir) { //check arguments _stack = new FastStack<File>(); _stack.push(baseDir); _next = new ArrayList<File>(); } private void searchNext() { while (_next.isEmpty() && !_stack.isEmpty()) { File dir = _stack.pop(); String[] fileList = dir.list(); if (fileList == null) continue; for (int i = 0; i < fileList.length; i++) { File file = new File(dir, fileList[i]); _next.add(file); if (file.isDirectory()) _stack.push(file); } } } public boolean hasNext() { if (_next.isEmpty() && !_stack.isEmpty()) searchNext(); return !_next.isEmpty(); } public File next() { if (!hasNext()) throw new NoSuchElementException(); return _next.remove(0); } public void remove() { throw new UnsupportedOperationException("Not implemented"); } }
(по материалам форума RSDN.ru)
Здесь _stack выделяется в куче (в динамической памяти), к нему, естественно, обращения будут происходить в несколько раз затратнее (как к любому другому объекту), чем если бы он не использовался, и все вычисления происходили в переписанном чисто рекурсивном методе searchNext().

Кстати, есть одна особенность в оптимизации рекурсии по стэку.
Например, в этой конструкции:
class DemoFactorial { public int factorial (int n) { return _factorial(n, 1); } public int _factorial(int n, int result) { if (n <= 0) { return 1; } else { return _factorial(n - 1, n * result); } } }
используются ДВА метода вместо одного, как здесь:
class DemoFactorial { public int _factorial(int n, int result) { if (n <= 0) { return 1; } else { return n * factorial(n - 1); } } },
только из-за того, что хвостовой вызов позволяет использовать очень мощную оптимизацию в данном случае на уровне JVM: произвести замену стэкового фрейма, сформированного для вызывающего метода, стэковым фреймом для вызываемого метода. Таким образом можно значительно сократить глубину стэка во время работы программы, предотвращая переполнение стэка для рекурсивных хвостовых вызовов.

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

← →
Nikolay M. © (2006-03-18 17:56) [11]

> Я и спрашивал мнение участников о НЕОБХОДИМОСТИ. Т. е. Где
> не заменишь.

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

← →
iZEN © (2006-03-18 17:59) [12]

Исправляяю неверно написанный от руки пример с одним методом:
class DemoFactorial { public int factorial(int n) { if (n <= 0) { return 1; } else { return n * factorial(n - 1); } } }

← →
Alexander Panov © (2006-03-18 18:01) [13]

> еще хуже GOTO.

Только не надо пропагандировать свои взгляды в виде непогрешимых истин.
Всему свое место и время. В том числе рекурсии и GOTO.

← →
Marser © (2006-03-18 18:07) [14]

Рекурсия это красиво, прежде всего. И проще в реализации нередко. Но стэк жрёт...
GOTO, наоборот некрасиво и моветон, но это вообще альфа и омега программирования, хотя это сложно понять, не спустившись несколькими этажами ниже, в мир ассемблера.

← →
Virgo_Style © (2006-03-18 18:12) [15]

надо где надо - делать как надо, а где не надо - как не надо не делать. Есть другие мнения?

%-)

← →
Nikolay M. © (2006-03-18 18:14) [16]

> Alexander Panov © (18.03.06 18:01) [13]
> Только не надо пропагандировать свои взгляды в виде непогрешимых
> истин.
> Всему свое место и время. В том числе рекурсии и GOTO.

Только не надо мои посты возводить в степень непогрешимых истин.
Непогрешимая истина, конечно, в том, что всему место и время. Опубликуй, плз, весь список своих истин, чтобы, не дай вдруг, глупость как-нибудь не сказать...

← →
GanibalLector © (2006-03-18 19:41) [17]

> Я и спрашивал мнение участников о НЕОБХОДИМОСТИ. Т. е. Где не заменишь.

Да пожалуйста. При программировании шахмат\шашек и др.логических игр...в частности в алгоритме alpha-beta! Дабы не было переполнения,в подобные алгоритмы заложена глубина(обычно не более 9)

← →
TStas © (2006-03-18 20:41) [18]

К своему стыду не знаю С++, но был очень удивлен возможностью обхода дерева без рекурсии

← →
Alexander Panov © (2006-03-18 20:42) [19]

> Nikolay M. © (18.03.06 18:14) [16]
> Непогрешимая истина, конечно, в том, что всему место и время.
> Опубликуй, плз, весь список своих истин, чтобы, не дай
> вдруг, глупость как-нибудь не сказать...

Да не обижайся.

Одну непогрешимую ты только что сказал. Или ты не уверен в том, что она таковой является?

Про Goto кто-то сказал, что это некрасиво, а остальные, как попугаи, повторяют.

С рекурсией по-другому.
Но и с ней то же самое - всему свое место и время.

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

← →
Nikolay M. © (2006-03-18 21:00) [20]

> Alexander Panov © (18.03.06 20:42) [19]

"Авторитет" говорит, что без рекурсии обойтись можно. Мой опыт говорит, что не только можно, но и нужно. В 99.99% случаев.

← →
TStas © (2006-03-18 21:03) [21]

И я считаю, что рекурсия - крайнее средство для чего-то древовидного.
GOTO при переделке кода. Все хорошо вмеру и к месту.

← →
iZEN © (2006-03-18 21:05) [22]

>TStas © (18.03.06 20:41) [18]
>К своему стыду не знаю С++, но был очень удивлен возможностью обхода дерева без рекурсии.

В сообщении iZEN © (18.03.06 17:53) [10] все примеры на Java.

← →
isasa © (2006-03-18 21:08) [23]

Напоминает спор: что лучше использовать - for ... while ... repeat ... ?
Использование операторов диктуется логикой конкретного алгоритма и его требований. Не более.
Что лучше x*x <-> sqr(x), x+x <-> 2*x ? ;)

← →
jack128 © (2006-03-18 21:18) [24]

TStas © (18.03.06 20:41) [18]
К своему стыду не знаю С++, но был очень удивлен возможностью обхода дерева без рекурсии

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

Nikolay M. © (18.03.06 17:12) [7]
использовал ее последний раз лет 5 назад
не фига себе..ты что, за 5 лет не разу с деревьями не работал?

← →
Sergey Masloff (2006-03-18 21:19) [25]

jack128 © (18.03.06 21:18) [24]
>хотя Mbo с свое время подкинл мне рекурсионную функцию
не осталось?

← →
Nikolay M. © (2006-03-18 21:35) [26]

> isasa © (18.03.06 21:08) [23]
> Напоминает спор: что лучше использовать - for ... while
> ... repeat ... ?
> Использование операторов диктуется логикой конкретного алгоритма
> и его требований. Не более.
> Что лучше x*x <-> sqr(x), x+x <-> 2*x ? ;)

Твои примеры и рекурсия без рекурсии - разные вещи.

> jack128 © (18.03.06 21:18) [24]
> в этой ветке ветке уже говорили, что рекурсию можно заменить
> циклом. хотя Mbo с свое время подкинл мне рекурсионную функцию,
> которую я так и не смог в цикл преобразовать..
>
> не фига себе..ты что, за 5 лет не разу с деревьями не работал?

Да, было что-то такое рекурсивную функцию. Кажется, сделали в итоге циклом.

С деревьями работал, как-то обходился.

← →
MBo © (2006-03-19 08:00) [27]

>Sergey Masloff (18.03.06 21:19) [25]
>.jack128 © (18.03.06 21:18) [24]
>хотя Mbo с свое время подкинл мне рекурсионную функцию
>не осталось?

функция Аккермана Ack(m, n) определяется для целых m>=0, n>=0 условиями:
Ack(0, n) = n+1,
Ack(m, 0) = Ack(m-1,1) при m > 0,
Ack(m, n) = Ack(m-1, Ack(m,n-1)) при m, n > 0.

← →
TUser © (2006-03-19 08:43) [28]

Ack(0, n) = 2 ^ n

(c) Кормен

Точнее так

Akk (1, j) = 2 ^ i
Akk (i, 1) = Akk (i - 1, 2)
Akk (i, j) = Akk (i - 1, Akk (i, j - 1))

Ну, значит люди по-разному рисуют. [30] я проверил - страница 424.

Ну и что? Функцию Аккермана нельзя вычислить без рекурсии?

> но создание НЕНУЖНОГО массива...

Статический массив создаётся при загрузке программы, т.е. стоимость = 0
Локальный массив создаётся одной машиной инструкцией, т.е. стоимость = ~0

По времени массивы очень малозатратны...

>palva © (19.03.06 09:12) [32]
>Ну и что? Функцию Аккермана нельзя вычислить без рекурсии?

Очень трудно получить нерекурсивный аналог.

> Очень трудно получить нерекурсивный аналог.
Ну я не так спросил.
Разве трудно написать нерекурсивную программу?

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

> любую рекурсию можно свести к циклу.

Как-то встретилась задача, решение которой сводилось к многоуровневому циклу:
for i := ... to ... do for j := ... to ... do for k := ... to ... do for l := ... to ... do for m := ... to ... do for n := ... to ... do и т.д.
Сложность состояла в том, что количество вложенных циклов могло быть рассчитано только на этапе исполнения. Решил так - написал рекурсивную процедуру, которая содержит один цикл и из этого цикла вызывает сама себя, если не выполнено условие завершения:
procedure Proc (...); begin ... for i := ... to ... do if <еще_не_конец> then Proc(...) ... end;
Как в этом случае обойтись без рекурсии (либо ее "ручной" реализации через стек, что, по сути, то же самое)?

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

Любую идею можно довести до абсурда.
Давайте еще и от циклов откажемся, заменив их на if+goto?
(Кстати, вот только что вспомнил, как на заре своей программистской юности упорно отрицал необходимость циклов, используя именно такую комбинацию. Дело было еще на Basic"е).

Я считаю рекурсию красивым и удобным решением.

Кому мало стека - или {$MAXSTACKSIZE number}, или динамически выделять память.

> Как в этом случае обойтись без рекурсии (либо ее "ручной" реализации через стек, что, по сути, то же самое)?

Часто подобные задачи сводятся к получению следующего значения, например
for i:="0" to "9" do
for j:="0" to 9 do
for k:="0" to 9 do
...
writeln (i, j, k, ...);
можно переписать
s:="000";
repeat
writeLn (s);
until not Next (s);

РЕальная необходимость рекурсии Найти похожие ветки