Не хочу рекурсию

← →
QuasiLamo © (2005-11-03 13:34) [0]

Есть дерево, хранится в таблице (посредством полей id и parent_id). Надо отобразить дерево, не прибегая к рекурсивным алгоритмам.
Сижу, думаю...но мне кроме рекурсии ничего в голову не лезет... кому нечем заняться - присоединяйтесь... :)

← →
msguns © (2005-11-03 13:41) [1]

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

;)

← →
Sergey13 © (2005-11-03 13:41) [2]

А чем рекурсия не подходит? Что за БД?

← →
Nikolay M. © (2005-11-03 13:42) [3]

http://www.sql.ru/forum/actualthread.aspx?tid=230808&hl=%e4%e5%f0%e5%e2%ee

← →
КаПиБаРа © (2005-11-03 13:47) [4]

Вроде рекурсию всегда можно на цикл заменить

← →
QuasiLamo © (2005-11-03 13:49) [5]

> Sergey13 © (03.11.05 13:41) [2]

MySQL
(+PHP)

А рекурсия щас есть... мне кажется это будет тормозить, когда дерево достаточно разрастется

← →
QuasiLamo © (2005-11-03 13:53) [6]

> Вроде рекурсию всегда можно на цикл заменить

надо вывести последовательно, с соблюдением иерархии, если бы можно было любым выведеным узлам сыновей добавлять, я бы просто прошелся ты по всей таблице

← →
КаПиБаРа © (2005-11-03 13:54) [7]

msguns © (03.11.05 13:41) [1]
Только зубами

Попроси соседа почесать зубами твой локоть :)

← →
jack128 © (2005-11-03 13:55) [8]

КаПиБаРа © (03.11.05 13:47) [4]
Вроде рекурсию всегда можно на цикл заменить
это если доступны структуры типа стека или хотя бы дин массива. Насколько это реализуемо в mysql и php - не знаю..

← →
Nikolay M. © (2005-11-03 13:55) [9]

> надо вывести последовательно, с соблюдением иерархии

Ты ответы читаешь?

← →
Sergey13 © (2005-11-03 13:57) [10]

2[5] QuasiLamo © (03.11.05 13:49)
Если полное дерево (т.е. всю таблицу) выводить - по любому будет тормозить. Если ветки отдельные, то я денормализацией маленькой ускорял на порядок.

← →
MBo © (2005-11-03 14:02) [11]

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

>КаПиБаРа © (03.11.05 13:47) [4]
>Вроде рекурсию всегда можно на цикл заменить

Хочешь потренироваться на функции Аккермана? ;)

← →
QuasiLamo © (2005-11-03 14:04) [12]

> Nikolay M. © (03.11.05 13:55) [9]

читаю ссылку вашу, ищу в том форуме

← →
jack128 © (2005-11-03 14:07) [13]

MBo © (03.11.05 14:02) [11]
Хочешь потренироваться на функции Аккермана?

А хочу. Есть готовая рекурсивная реализация на паскале ??

← →
jack128 © (2005-11-03 14:11) [14]

Все, нашел уже. На выходных поковыряю..

← →
MBo © (2005-11-03 14:15) [15]

jack128 © (03.11.05 14:07) [13]

function Akk(m,n:Integer):Integer; begin if m = 0 then Result := n+1 else if n = 0 then Result := Akk(m - 1, 1) else Result := Akk(m - 1, Akk(m, n - 1)); end;

← →
jack128 © (2005-11-03 14:53) [16]

Мдя. Красивая функция. А какая неприметная на вид...

← →
Sandman29 © (2005-11-03 14:53) [17]

function Akk1(m, n: Integer): Integer; begin while m <> 0 do begin if n = 0 then begin Dec(m); n := 1; end else begin n := Akk1(m, n - 1); Dec(m); end; end; Result := n + 1; end;
Дальше застрял. Если запоминать текущие значение n и m, то по сути получим ту же рекурсию.

← →
oldman © (2005-11-03 14:56) [18]

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

почему, объясни...

← →
Sandman29 © (2005-11-03 14:58) [19]

jack128 © (03.11.05 14:53) [16]

Она не красивая, она убийственная. Задал аргументы 3,2 - за доли секунды сработала, задал 4,2 - не дождался ответа. Вставил Memo.Lines.Add, посмотрел вывод и понял, что на интуитивном уровне смысл функции не понимаю. Хотя название знакомое :)

← →
DiamondShark © (2005-11-03 15:01) [20]

> задал 4,2 - не дождался ответа

А я сразу -1, -1 попробовал ;)

← →
jack128 © (2005-11-03 15:06) [21]

Sandman29 © (03.11.05 14:53) [17]
Если запоминать текущие значение n и m, то по сути получим ту же рекурсию

В свое время я сделал просто - когда рекурсия идет в глубь - все аргументы и прмежуточные переменные пихал в стек(TStack), а при раскрутке рекурсии соответственно вынимал их из стека. Цикл завершался когда Stack.Count = 0. В данном случае проблема в том, что даже для того, чтобы вычислить новое значение аргумента рекурсии нужно снова её запустить.
MBo © (03.11.05 14:15) [15]
function Akk(m,n:Integer):Integer;
begin
if m = 0 then
Result := n+1
else
if n = 0 then
Result := Akk(m - 1, 1)
else
Result := Akk(m - 1, Akk(m, n - 1)); // Проблема здесь!
end;

Но наверно алгоритм можно модифицировать и под такой случай.. Будем думать, но не работе ;)

← →
jack128 © (2005-11-03 15:08) [22]

Я, кстати, начал запускать функцию с 10, 10 :-)))

← →
QuasiLamo © (2005-11-03 15:14) [23]

> Sandman29 © (03.11.05 14:58) [19]
> jack128 © (03.11.05 14:53) [16]

опять разговор ушел не туда

> oldman © (03.11.05 14:56) [18]
>
> > Надо отобразить дерево, не прибегая к рекурсивным алгоритмам.
>
>
>
> почему, объясни...

QuasiLamo © (03.11.05 13:49) [5]

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

← →
Sandman29 © (2005-11-03 15:28) [24]

jack128 © (03.11.05 15:06) [21]

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

QuasiLamo © (03.11.05 15:14) [23]
Видимо, качественно по другому все равно не сделать, а изменять структуру данных мне лень...
Можно параллельно вести таблицу-линейный индекс дерева. Тогда вместо рекурсии можно будет использовать foreach.

← →
jack128 © (2005-11-03 17:17) [25]

Sandman29 © (03.11.05 15:28) [24]
то я не вижу смысла избавляться от рекурсии.
Ну задача такая - избавиться рекурсивного вызова при вычислени данной функции:
MBo © (03.11.05 14:02) [11]
>Вроде рекурсию всегда можно на цикл заменить

Хочешь потренироваться на функции Аккермана? ;)

QuasiLamo © (03.11.05 15:14) [23]
Хотя те, кто любят пофлудить еще наверно порезвяца ;)
:-P

← →
Igorek © (2005-11-03 19:10) [26]

> jack128 © (03.11.05 15:06) [21]

var R: Integer; begin ... R := Akk(m, n - 1); Result := Akk(m - 1, R);

Не всегда есть необходимость вычитывать и отражать все дерево сразу. Достаточно один уровень. Потом при активации узла - считать еще один ЕГО уровень. Это и ресурсы экономит (все дерево сразу ОЧЕНЬ редко надо), и чтение из БД легко делается, ибо parent_id в каждый момент времени один и известен.
Подумай...

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

> ИМХО дерево чего-то - единственный случай, где рекурсия
> необходима

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

to Igorek © (03.11.05 19:55) [29]:
>Любая рекурсия физически реализуется через стек вызовов.
>Соотв. можно ее явно заменить стеком.
Именно. Я как-то раз QuickSort в итерацию разворачивал. Развернуть-то развернул, но пришлось что-то типа стека использовать для временного хранения промежуточных параметров.

Desdechado © (03.11.05 19:36) [27]
Потом при активации узла - считать еще один ЕГО уровень. Это и ресурсы экономит (все дерево сразу ОЧЕНЬ редко надо)
В простой программе - да. Но в web трудноёмко прикрутить очередное считывание данных по клику где-то. Либо замучаешься выирисовывать на экране дерево средствами html, либо замучаешься в скрипте каждый раз генерировать новую ветку дерева (запоминая, что было открыто ранее).

Ну и чем же стек отличается от рекурсии?
Да ничем! Это его эмуляция!

Не проверял, написал сходу в блокноте:

m,n _begin: if (m = 0) then R := n + 1 else begin if (n = 0) then begin push(m, n); m := m - 1; n := 1; ret := 0; goto _begin; end else begin push(m, n); m := m; n := n - 1; ret := 1; goto _begin; _resume1: ret := 0; m := m - 1; n := R; goto _begin; end; end; pop(m, n); case ret of 0: ; 1: goto _resume1; end;

Без стека никак. (?)

Блин, отступы посъедались.

>>Sandman29 © (03.11.05 14:58) [19]

>задал 4,2 - не дождался ответа.

А я дождался. Ответ был "Stack Overflow" :o)
Потом увеличил Max Stack Size до максимума, подождал минут 5 - не дождался, на работу уже пора.

Lamer@fools.ua © (04.11.05 09:32) [35]

Я проще поступил - через пару минут ожидания поставил точку останова и посмотрел стек вызовов. Удивился, запустил дальше. Еще через пару минут опять посмотрел стек вызовов - удивился еще больше, так как было показано почти то же самое. Понял, что ждать можно до пенсии и плюнул на это дело :)

>>Sandman29 © (04.11.05 10:31) [36]

>Я проще поступил - через пару минут ожидания поставил точку останова и посмотрел стек вызовов.
У меня времени не было. Я за 5 минут до выхода из дома запускал :o)

> MBo © (03.11.05 14:15) [15]

Все еще хуже
Функция Аккермана Akk (1,j) = 2^j Akk (i,1) = Akk (i-1,2) Akk (i,j) = Akk (i-1,Akk (i,j-1)) при i, j >= 2 (c) из Кормена

Не хочу рекурсию Найти похожие ветки