Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / FoxPro, Visual FoxPro [игнор отключен] [закрыт для гостей] / Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию? / 13 сообщений из 13, страница 1 из 1
20.11.2007, 01:52
    #34950476
prohodil_mimo
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
Cтояла задача - написать программу для генерации многоуровневого меню без ограничения уровня вложенности.
Данное меню потом выводит javascript-программа на страницу ресурса (html/htm-страницу).
Т.е. необходимо было специальным образом сформировать некий текст, что бы его потом:
а) БЕЗ ПРОБЛЕМ (без ошибок) схавала javascript-программа, которая , к тому же,
б) правильно бы вывела меню на страницу.
Программа-редактор меню написана на FoxPro, и по дизайну НЕСКОЛЬКО напоминает сам FoxPro-шный редактор :)

НО дело не в программе, а в подпрограмме обработки дерева.

При работе используется таблица, где есть:
id - уникальный идентификатор
parent_id - родитель
order - сортировка в пределах ветви (т.е. в пределах одного родителя)

Что такое дерево?
Есть родитель (например, у него него уникальный идентификатор - id = 1)
Есть дочерние (childe) ветви (у них parent_id=1), которые в пределах родителя упорядочены по order, и у которых свои уникальные идентификаторы и, которые, в свою очередь сами могут быть родителями и иметь свои дочерние ветви и т.д.

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

Понимаю, что в который раз открываю Америку, НО ХОЧУ ОБРАТИТЬ внимание, что в этом случае ЗНАЧИТЕЛЬНО сокращается и упрощается программный код.
Еще замечание - все переменные должны быть определены как LOCAL, в этом случае не возникнет ошибок, связанных с пересечением области действия (жизни?) переменных.

Пример рекурсии (точнее результат применения), находится вот здесь
http://www.maple4.ru/i_menus.htm

А где лично Вы применяли рекурсию?
P.S. Прошу не считать данное сообщение, как рекламу. Автор исходит из того, что лучше один раз увидеть (а еще лучше - потрогать :) ), чем сто раз услышать.
...
Рейтинг: 0 / 0
20.11.2007, 09:37
    #34950705
PaulWist
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
prohodil_mimo
А где лично Вы применяли рекурсию?


Ну.., например если Вы сталкивались с производством, то знаете, что готовое изделие состоит из составляющих, вот можете добавить - рекрсия при обработке готового изделия
...
Рейтинг: 0 / 0
20.11.2007, 10:56
    #34950995
Burn
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
Рекурсия вещь, в теории, отличная. Но на практике огрничена размером стека вызовов. Особено это болезнено для Фокса, у которого ваще ограничение на 50 вложеных DO. Но если Вы уверены что вам этого достаточно то можно.
У меня работает в одном месте - расчет плановых цен и себестоимости, когда одно из собственых изделий является полуфабрикатом для следующего. Но у меня метизка. А у нее своя специфика - очень короткая производственая цепочка при крайне широкой номенклатуре. Если таких звеньев много то легко вывалится за ограничения
...
Рейтинг: 0 / 0
20.11.2007, 11:16
    #34951101
piva
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
BurnОсобено это болезнено для Фокса, у которого ваще ограничение на 50 вложеных DO.
Я наверное что-то пропустил ?
автор
Maximum # of nested DO calls.

Tip
You can change the default level of nesting by using a configuration file that includes the STACKSIZE setting. For more information, see Special Terms for Configuration Files.

128 (Default)

STACKSIZE = nValue
Specifies the number of nesting levels from 32 to 64,000 for operations such as the DO command.

Я ставил 64000 но при уровне вложенности около 800 - 9ка просто падала с ошибкой
...
Рейтинг: 0 / 0
20.11.2007, 11:27
    #34951165
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
prohodil_mimoА где лично Вы применяли рекурсию?

Рекурсия наилучший алгоритм для обработки деревьев, обычно для этого и применяется. Код получается очень простой, в отличии от других способов работы с деревьями.
Бояться ее не надо, надо просто понимать как она работает, в т.ч. про область видимости переменных, указатели в таблицах, ссылки на объекты.

prohodil_mimoP.S. Прошу не считать данное сообщение, как рекламу
Реклама рекурсии - это оригинально
...
Рейтинг: 0 / 0
20.11.2007, 11:33
    #34951196
Kruchinin Pahan
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
piva

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

Вырожденный пример хвостовой рекурсии - переход от листа дерева к его корню по ключам родителя. Организуется как обычный цикл, при этом, стек, как таковой, не нужен. Используется только верхушка стека (тобишь, текущий элемент).
...
Рейтинг: 0 / 0
20.11.2007, 11:47
    #34951268
piva
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
Kruchinin PahanВообще, иногда выгодней применять хвостовую рекурсию. Правда, в таком случае, эмуляция стека целиком лежит на программисте. Я не понял - это тут меня учат как делать рекурсию без рекурсии что ли ? Спасибо конечно, но это я уже давно практикую в некоторых случаях когда есть возможность "выпасть" за 128 уровней вложенности
...
Рейтинг: 0 / 0
20.11.2007, 13:20
    #34951716
Valerii
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
Я написал свою рекурсию на фоксе - нет ограничений на вложенность структур...
Использую для создания TreeView справочников. Но сам контрол медленно начинает работать при 10 тыс значений.
кОМУ ИНТЕРЕСОНО - ОСТАВЬТЕ СВОЙ ПОСТ.
...
Рейтинг: 0 / 0
20.11.2007, 17:22
    #34952886
proshel_mimo
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
В копилку знаний :)
Как вывести дерево на экран

создаются 2 программы proc1 и proc2
нужна tablica.dbf
create table tablica (id_ n(15), parent_id n(15), order n(15), prompt c(100))
и заполняем данными ....
или в zip-е работающий пример

далее запускается proc1
************
do proc1
************

Тексты процедур
proc1
******************
CLOSE ALL
CLEAR
use tablica EXCLUSIVE
index on parent_id*1000000+order tag poradok
do proc2 with 0

proc2
******************
lparameters parent_
local t_recno

scan for parent_id=parent_
? prompt
t_recno=recno()
do proc2 with id_
go t_recno
endscan
return
...
Рейтинг: 0 / 0
20.11.2007, 17:41
    #34952966
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
proshel_mimoВ копилку знаний :)
...
Не надо делиться банальными решениями. Тем более идеологически неполноценными. Вот эта строчка:
Код: plaintext
index on parent_id* 1000000 +order tag poradok
1. Кто сказал что order менее 1000000? Для абстракного примера не должно быть ограничений
2. Почему узлы сортируются по parent_id, а не по order как листья дерева? Не получилось?

PS Кодом тоже не надо спамить, один твой пост с рекламой мапела уже забанили.
...
Рейтинг: 0 / 0
20.11.2007, 18:02
    #34953053
proshel_mimo
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
Dima T proshel_mimoВ копилку знаний :)
...
Не надо делиться банальными решениями. Тем более идеологически неполноценными. Вот эта строчка:
Код: plaintext
index on parent_id* 1000000 +order tag poradok
1. Кто сказал что order менее 1000000? Для абстракного примера не должно быть ограничений
2. Почему узлы сортируются по parent_id, а не по order как листья дерева? Не получилось?

PS Кодом тоже не надо спамить, один твой пост с рекламой мапела уже забанили.
Во первых , как я понял, Dima T - истина в последней инстанции :)
Во вторых , может быть загрузить приложенный файл (recursia.zip) и посмотреть пример (т.е. как заполнена таблица)?
Тогда (хотел сказать "может быть") станет понятно, что в примере нет деления на узлы и листья
В третьих ,
вместо

use tablica EXCLUSIVE
index on parent_id*1000000+order tag poradok


я бы сделал лучше
select * from tablica order by parent_id,order into cursor bbk && реклама BBK :)

в четвертых, order -это порядок в группе (одного родителя)
поэтому, для изменения порядка вывода на экран достаточно поменять order в группе
...
Рейтинг: 0 / 0
20.11.2007, 20:52
    #34953504
Burn
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
piva[Я наверное что-то пропустил ?
Это похоже я чтото пропустил :-(
Синкс. Пошел перечитывать хелп
...
Рейтинг: 0 / 0
21.11.2007, 05:49
    #34953820
Kruchinin Pahan
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию?
piva Kruchinin PahanВообще, иногда выгодней применять хвостовую рекурсию. Правда, в таком случае, эмуляция стека целиком лежит на программисте. Я не понял - это тут меня учат как делать рекурсию без рекурсии что ли ? Спасибо конечно, но это я уже давно практикую в некоторых случаях когда есть возможность "выпасть" за 128 уровней вложенности
Просто напоминаю еще одно прикольное словечко, которым можно юзверей пугать: "Ууу... Да здесь вам хвостовая рекурсия только поможет!" ;)
...
Рейтинг: 0 / 0
Форумы / FoxPro, Visual FoxPro [игнор отключен] [закрыт для гостей] / Боязнь рекурсии. Да, было и такое. Для чего вообще можно применить рекурсию? / 13 сообщений из 13, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]