Бесконечная рекурсия

@Tanyusha · Регистрация: 08.08.2014

Студворк — интернет-сервис помощи студентам

Здравствуйте, уважаемые форумчане!
Подскажите, пожалуйста, как избежать бесконечной рекурсии.
С помощью рекурсии заполняю treeView WPF C# из таблицы базы MS SQL. Пользователь может добавлять, копировать и удалять элементы дерева.
В таблице Sql храню ссылки между элементами.
Получается ситуация:

ID ParentID ChildID

1 121 122

2 122 121

Если на первом уровне я могу проанализировать ситуацию, то во вложенности на уровнях глубже у меня не получается
Подскажите, пожалуйста, как можно предотвратить бесконечную рекурсию
Заранее спасибо

@qwertehok · 05.12.2019, 22:20

Сообщение от Tanyusha

как можно предотвратить бесконечную рекурсию

1) не делать ее в данных
2) прерывать по счетчику

@Tanyusha · 05.12.2019, 22:31 **[ТС]**

Сообщение от qwertehok

1) не делать ее в данных
2) прерывать по счетчику

qwertehok, как не делать в данных? Получается, что пользователь, может папку содержащую подпапку вложить в ту самую подпапку, а как это запретит программно на более глубоких уровнях я как раз не знаю. И где это запретить? когда пользователь пытается сделать такие добавления? И главное как?

@qwertehok · 05.12.2019, 23:23

Сообщение от Tanyusha

И где это запретить?

Сообщение от Tanyusha

И главное как?

а при чем ту MSSQL?

проблемы с сервером или с запросами есть? задавай

@Tanyusha · 06.12.2019, 08:44 **[ТС]**

qwertehok,
Могу точно сказать, что проблемы есть. Опыта работы с деревьями практически нет, поэтому не понимаю, что делаю не так

вот запрос на добавление узла, точнее на добавление связи подчиненного узла к родительскому:

SQL
1
2
3
IF(NOT EXISTS(SELECT 1 FROM[ARXIV].[dbo].[TreeLink] WHERE ([treeLink_idChild] ='" + childID + @"'AND [treeLink_idParent] = '" + parentID + @"') 
 OR ([treeLink_idChild] ='" + parentID + @"'AND [treeLink_idParent] = '" + childID + @"'))) 
 INSERT INTO[EL_ARXIV].[dbo].[TreeLink]([treeLink_idChild], [treeLink_idParent]) VALUES('" + childID + "','" + parentID + "')";

где childID - ID подчиненного узла, parentID - ID родительского узла

@invm · 06.12.2019, 08:51

Сообщение от Tanyusha

Подскажите, пожалуйста, как можно предотвратить бесконечную рекурсию

Стандартный способ - хранить для узла пройденный путь.
Если узел в пути уже был, прекращать рекурсию.

@Tanyusha · 06.12.2019, 09:25 **[ТС]**

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

@invm · 06.12.2019, 09:34

Tanyusha, не надо ничего хранить. Строить путь нужно динамически в вашей рекурсивной функции, там же и анализировать.

@Tanyusha · 06.12.2019, 09:50 **[ТС]**

invm,
вот моя рекурсивная функция, подскажите, пожалуйста, как ее надо переделать. Заранее спасибо

SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
WITH RecursiveTablFile ([object_ID], [description], [name], [file_Patch], [file_Izm], [treeLink_ID], [treeLink_idChild], [treeLink_idParent])
  AS
  (
    SELECT [objId],[des],[name],[patch],[izm],[linkid],[child],[parent]
    FROM [ARXIV].[dbo].[psFindFilesWithMaxIzm]
    WHERE [child] = @objectID 
 
    UNION ALL
        SELECT [objId],[des],fi.[name],[patch],[izm],[linkid],[child],[parent]
        FROM [ARXIV].[dbo].[psFindFilesWithMaxIzm] AS fi
        INNER JOIN RecursiveTablFile AS r
        ON [parent] = r.treeLink_idChild                            
  )

@invm · 06.12.2019, 10:37

Tanyusha, пример:

T-SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
declare @t table (id int, parent int);
 
insert into @t
values
 (1, null),
 (2, 1),
 (3, 1),
 (4, 3), 
 (5, 4), 
 (3, 5); -- петля
 
with t as
(
 select
  id, parent, ',' + cast(id as varchar(max)) + ',' as p
 from
  @t
 where
  parent is null
 
 union all
 
 select
  c.id, c.parent, t.p + cast(c.id as varchar(max)) + ','
 from
  t join
  @t c on c.parent = t.id
 where
  t.p not like '%,' + cast(c.id as varchar(max)) + ',%'
)
select * from t;

@Tanyusha · 06.12.2019, 14:38 **[ТС]**

invm,
Спасибо огромное, я переделала свою рекурсию, и все сработало
Скажите, пожалуйста, а как этот способ применить, если treeView заполняется не сразу, а дерево заполняется по мере открывания узелков, я что-то не могу сообразить
Мой запрос на заполнение дерева по узлам:

SQL
1
2
3
SELECT ob.[object_ID], [description], [name], fl.file_Sborka FROM[ARXIV].[dbo].[Objects] AS ob
      LEFT JOIN(SELECT[object_ID], [file_Sborka] FROM[ARXIV].[dbo].[Files]) AS fl ON ob.object_ID = fl.object_ID
      WHERE ob.[object_ID] IN (SELECT[treeLink_idChild] FROM [ARXIV].[dbo].[TreeLink] WHERE[treeLink_idParent] = '" + parentID + @"')

Добавлено через 26 минут
или контролировать путь во время добавления объектов и соответственно надо править запрос на добавление объектов?

@invm · 06.12.2019, 15:39

Сообщение от Tanyusha

дерево заполняется по мере открывания узелков

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

@Tanyusha · 06.01.2020, 12:34 **[ТС]**

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

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .

@Tanyusha 4 / 4 / 1 Регистрация: 08.08.2014 Сообщений: 83
	06.12.2019, 09:25 [ТС]
	invm, т.е. в Sql создать еще одну таблицу, в которой хранить пути для каждого узла, а потом анализировать на наличие конкретного пути в таблице при добавлении этого узла, в какой- нибудь другой узел? вы уже пробовали так делать? Надо анализировать на частичное совпадение пути? Вот картинка, бесконечной рекурсии. как может помочь хранение пути? Миниатюры 0

@invm 3614 / 2135 / 756 Регистрация: 02.06.2013 Сообщений: 5,169
	06.12.2019, 09:34
	Tanyusha, не надо ничего хранить. Строить путь нужно динамически в вашей рекурсивной функции, там же и анализировать. 0

@Tanyusha 4 / 4 / 1 Регистрация: 08.08.2014 Сообщений: 83
	06.01.2020, 12:34 [ТС]
	Подскажите, пожалуйста, как избежать бесконечной рекурсии при добавлении узлов дерева. Наверное, как не позволять добавлять такие узлы, которые в дальнейшем могут привести к бесконечной рекурсии. Заранее спасибо 0