gifts2017

Рекурсия в 1С и управление деревом значений

Опубликовал Ярослав Волохов (YVolohov) в раздел Программирование - Практика программирования

Термин «рекурсия» используется во многих областях знаний. В программировании рекурсия – вызов процедуры (функции) из нее же самой. Статья рассказывает об использовании рекурсии в 1С Предприятии для работы с деревом значений.

 

Термин «рекурсия» используется во многих областях знаний. В программировании рекурсия – вызов процедуры (функции) из нее же самой. Различают простую и сложную рекурсию. При простой рекурсии некоторая процедура А вызывает сама себя, пока не выполниться заданное условие выхода, или же бесконечно. В случае сложной рекурсии процедура А вызывает процедуру Б, которая опять вызывает процедуру А, и так далее до выполнения условия выхода или бесконечно. В сложной рекурсии может участвовать и больше двух процедур или функций.

Организовать рекурсию средствами встроенного языка 1С Предприятия очень легко. Вот пример простой рекурсии:

Процедура ПроцедураА()
   
ПроцедураА();
КонецПроцедуры

 А это сложная рекурсия:

Процедура ПроцедураА()
   
ПроцедураБ();
КонецПроцедуры

Процедура
ПроцедураБ()
   
ПроцедураА();
КонецПроцедуры

Оба фрагмента кода приведены исключительно для примера. При попытке их выполнить возникнет бесконечный цикл и, как результат, произойдет зависание системы, поскольку не задано условие выхода. Создадим рекурсию с условием выхода:

Процедура ВывестиЧисла(пЧисло)
    Если
пЧисло <= 100 Тогда
       
Сообщить(Строка(пЧисло));
       
пЧисло = пЧисло + 1;
       
ВывестиЧисла(пЧисло);
    Иначе
        Возврат;
    КонецЕсли;
КонецПроцедуры

ВывестиЧисла(1);

            Этот фрагмент кода выведет в окно служебных сообщений 1С Предприятия числа от 1 до 100. После этого выполниться условие выхода и программа будет завершена. Процедура вызовет сама себя ровно 100 раз. Количество таких вызовов процедуры или функции называется глубиной рекурсии.

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

Оборотной стороной этого довольно простого по структуре механизма является то, что рекурсивные вызовы не бесплатны — на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого обычно рекомендуется избегать рекурсивных программ, которые приводят к слишком большой глубине рекурсии.

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

В 1С Предприятии 8.х рекурсия может быть использована для решения задач управления деревом значений. Например, мы интерактивно изменяем пометку элемента, который находиться на одном из верхних уровней дерева значений. В таком случае пометки должны программно устанавливаться (или сниматься) и для всех подчиненных ему элементов, находящихся на более низких уровнях дерева.

Если максимальное количество уровней дерева известно, то эта задача может быть решена следующим образом:

Процедура ИзменитьПометкиПодчиненных(пГлавный)
   
Подчиненные1 = пГлавный.Строки;

   
// Первый уровень подчиненных
   
Для Каждого Подчиненный1 Из Подчиненные1 Цикл
       
Подчиненный1.Пометка = пГлавный.Пометка;
       
Подчиненные2 = Подчиненный1.Строки;

       
// Второй уровень подчиненных
       
Для Каждого Подчиненный2 Из Подчиненные2 Цикл
           
Подчиненный2.Пометка = пГлавный.Пометка;
           
Подчиненные3 = Подчиненный2.Строки;

           
// Третий уровень подчиненных
           
Для Каждого Подчиненный3 Из Подчиненные3 Цикл
               
Подчиненный3.Пометка = пГлавный.Пометка;
            КонецЦикла;
        КонецЦикла;
    КонецЦикла;
КонецПроцедуры

Приведенная выше процедура устанавливает или снимает пометки у четырехуровневого дерева. Обход элементов дерева выполняется в трех вложенных друг в друга циклах. В качестве параметра «пГлавный» мы передаем строку верхнего уровня дерева значений, затем получаем подчиненные строки переданной строки и устанавливаем пометки. Затем получаем подчиненные строки каждой подчиненной строки, снова устанавливаем пометки, и т. д.

А если усложнить задачу?  Если максимальное количество уровней дерева неизвестно или так велико, что использовать вложенные циклы просто неэффективно, код получиться слишком громоздкий, да еще и повторяющийся? Ведь, по сути, для каждого уровня дерева значений выполняется одна и та же последовательность действий. Вот тут нам на помощь и придет рекурсия. В данном случае достаточно будет использовать простую рекурсию.

Процедура ИзменитьПометкиПодчиненных(пГлавный)
   
Подчиненные = пГлавный.Строки;
    Для Каждого
Подчиненный Из Подчиненные Цикл
       
Подчиненный.Пометка = пГлавный.Пометка;
       
ИзменитьПометкиПодчиненных(Подчиненный);
    КонецЦикла;
КонецПроцедуры

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

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

Процедура ИзменитьПометкиПодчиненных(пГлавный)
   
УровеньА = Новый Массив;
   
УровеньБ = Новый Массив;
   
УровеньА.Добавить(пГлавный);
    Пока НЕ (
УровеньА.Количество() = 0) Цикл
        Для Каждого
СтрокаДерева Из УровеньА Цикл
           
СтрокаДерева.Пометка = пГлавный.Пометка;
            Для Каждого
СтрокаДереваПодчиненная из СтрокаДерева.Строки Цикл
               
УровеньБ.Добавить(СтрокаДереваПодчиненная);
            КонецЦикла;
        КонецЦикла;
       
УровеньА = УровеньБ;
       
УровеньБ = Новый Массив;
    КонецЦикла;
КонецПроцедуры

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

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

Какой из описанных механизмов наиболее оптимален с точки зрения быстродействия? Ответ на этот вопрос может дать замер производительности.

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

При прочих равных условиях выполнение кода с использованием рекурсии заняло 0,086753 секунды, выполнение кода с использованием нескольких вложенных циклов – 0,050159 секунды, выполнение кода поуровневого обхода дерева – 0,087718 секунды.

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

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

           

http://www.infostart.ru/projects/4059/

 

            При подготовке статьи использованы материалы из:

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F

См. также

Подписаться Добавить вознаграждение

Комментарии

1. sound sound (sound) 30.06.09 14:27
однозначно чтобы понять рекурсию, надо понять рекурсию
imxored; denis_aka_wolf; Mi4man; hulio; BigMih; igor_gk; +6 Ответить 4
2. Евгений Люлюк (Evg-Lylyk) 30.06.09 14:36
Может так правильней ;)

Процедура ИзменитьПометкиПодчиненных(Строка)
Для Каждого Подчиненный Из Строка.Строки Цикл
Подчиненный.Пометка = пГлавный.Пометка;
ИзменитьПометкиПодчиненных(Подчиненный);
КонецЦикла;
КонецПроцедуры
3. Александр Венгер (venger) 30.06.09 14:37
(1) Это поможет:-))) http://infostart.ru/projects/4618/
Но, как доказано где-то когда-то и вроде как математически, любую задачу решаемую рекурсивно, можно решить итеративно и наоборот. Причем в 1С, уж в семерке так точно, рекурсия более затратна, чем цикл:-)
З.Ы. Ниче против статьи и ее автора не имею, просто ремарка:-)
4. Ярослав Волохов (YVolohov) 30.06.09 14:39
(2) Вобще то да, пара строчек балласта убрано :)
5. Александр Рытов (Арчибальд) 30.06.09 15:01
(3)>Но, как доказано где-то когда-то и вроде как математически, любую задачу решаемую рекурсивно, можно решить итеративно и наоборот.

Вот и скелет доказательства:
f(n+1)=g(f(n))
означает просто
f(n+1)=g(g(g(......g(1)....)
что реализуется циклом
f=g(1);
for i=1 to n loop
f=g(f);
endloop

И далее индукция по n...
6. Евгений Люлюк (Evg-Lylyk) 30.06.09 15:17
(3) рекурсия более понятна. На счет затратно сомневаюсь :). Хотелось бы увидеть замену рекурсии для варианта автора.
7. Александр Венгер (venger) 30.06.09 15:21
(6) Замерь две функции из первого поста отсюда: http://infostart.ru/forum/forum9/topic9906/messages/
И убедишься.
8. Евгений Люлюк (Evg-Lylyk) 30.06.09 15:22
(7) что на счет примера автора
9. Александр Венгер (venger) 30.06.09 15:28
(8) Что насчет замера? Какие результаты, в семерке, в восьмерке?
10. Евгений Люлюк (Evg-Lylyk) 30.06.09 15:30
(7) Для приведенного примера ИМХО рекурсия не нужна. Для примера автора пожалуйста
11. Евгений Люлюк (Evg-Lylyk) 30.06.09 15:31
(9) Так можно увидеть вариант автора без рекурсии
12. Александр Венгер (venger) 30.06.09 15:34
(10) Причем тут одно к другому, давайте разбираться последовательно, Вы выразили сомнения в том, что рекурсия затратнее цикла, Вам предложен чистый эксперимент, без инородных влияющих факторов. Каковы результаты?
13. Евгений Люлюк (Evg-Lylyk) 30.06.09 15:40
(12) В приведенном примере рекурсия не нужна.
Вы пишите "Причем в 1С, уж в семерке так точно, рекурсия более затратна, чем цикл:-)" т.е. утверждаете что рекурсия более затратна, хотелось бы видеть для варианта автора
14. Ярослав Волохов (YVolohov) 30.06.09 15:41
Предлагаю простое сравнение, нужно написать программу которая выводит числа от 1 до 100 с помощью цикла и с помощью рекурсии и сделать замер производительности.
15. Александр Рытов (Арчибальд) 30.06.09 15:43
(6, 10) В чем вопрос-то? Как обойти дерево без рекурсии? Или насколько различаются по затратам рекурсивный обход и нерекурсивный?
16. Александр Венгер (venger) 30.06.09 15:46
17. Александр Венгер (venger) 30.06.09 15:47
(15) Как обойти дерево без рекурсии, а то человек волнуется и все одно и тоже повторяет, своих ошибок признать не хочет:-)))
18. Dmitry Dmitry (Dimasik2007) 30.06.09 15:47
А кто-нибудь замерял глубину стека в 1С?
19. Ярослав Волохов (YVolohov) 30.06.09 15:52
Итак, с использованием рекурсии:

Процедура ВывестиЧисло(пЧисло)
Если пЧисло > 100 Тогда
Возврат;
Иначе
Сообщить(Строка(пЧисло));
пЧисло = пЧисло + 1;
ВывестиЧисло(пЧисло);
КонецЕсли;
КонецПроцедуры

ВывестиЧисло(1);

0,1154 сек.

Без использования рекурсии

Для Счетчик = 1 По 100 Цикл
Сообщить(Строка(Счетчик));
КонецЦикла;

0,1118 сек.

Почти одинаково, но рекурсия все же работает немного быстреее

20. Ярослав Волохов (YVolohov) 30.06.09 15:53
(19) рекурсия работает немного медленнее
21. Евгений Люлюк (Evg-Lylyk) 30.06.09 15:53
(16) тем что там рекурсия не нужна. ИМХО когда рекурсия необходима ее замена не будет эффективней.
22. Евгений Люлюк (Evg-Lylyk) 30.06.09 15:55
(19) Пример жесть!!! :)))) пожалуйста НА ПРИМЕРЕ АВТОРА ТЕМЫ
23. Ярослав Волохов (YVolohov) 30.06.09 15:57
24. Евгений Люлюк (Evg-Lylyk) 30.06.09 15:58
(17) "Как обойти дерево без рекурсии, а то человек волнуется и все одно и тоже повторяет, своих ошибок признать не хочет:-)))" в чем моя ошибка поясните пожулайста.
25. Александр Рытов (Арчибальд) 30.06.09 16:01
(17)Заводим два списка ссылок: на текущий уровень и на подчиненный. Первоначально первый список содержит сылку на корень, второй пуст.
Цикл пока не пуст первый список
Цикл по элементам первого списка
Тело: пометить подчиненные и загнать их во второй список
Конец вложенного цикла
Второй список сделать первым
Завести второй пустой список
Конец внешнего списка.
26. Ярослав Волохов (YVolohov) 30.06.09 16:02
рекурсия 0,092427
цикл 0,056335
Но это ни о чем не говорит, да в цикле быстрее, но зато рекурсия дает дополнительные возможности. Если дерево очень большое, или размер дерева неизвестен кроме рекурсии ничего больше использовать просто нельзя.
27. Александр Рытов (Арчибальд) 30.06.09 16:03
28. Александр Венгер (venger) 30.06.09 16:03
(21),(22) Значит первое мы определили, при прочих равных рекурсия затратнее цикла, надеюсь Вы согласитесь:-) Причем родители в справочнике тоже дерево, по сути, чтоб Вы не питали иллюзий:-) Я про пример из форума, куда я давал ссылку, а если Вам лень замерить, то с Вами трудно говорить:-) Это раз:-)
Второе, для того, чтобы мне поиграться с обходом дерева значений, т.к. оно есть только в восьмерке, мне придется дома найти и поставить восьмерку и посмотреть, какие методы и т.п. есть у этого объекта или что оно там, ибо восьмерку в глаза не видел, так что вам придется подождать пока я найду, поставлю, поиграюсь с восьмеркой. Или восьмерошники выдадут быстрее. Так что подождите. Но по поводу затратности рекурсии по сравнению с циклом при прочих равных мы убедились или еще сомневаемся?:-)))
29. Ярослав Волохов (YVolohov) 30.06.09 16:09
(27) а можно это выразить в коде
30. Александр Венгер (venger) 30.06.09 16:12
(22) +28, о вот выдали быстрее, чем я дома поставил восьмерку:-))) Пост 25-й Вас удовлетворил?:-))
31. Ярослав Волохов (YVolohov) 30.06.09 16:16
(30) меня не очень, хотелось бы увидеть это в коде
32. Александр Рытов (Арчибальд) 30.06.09 16:19
(29) Ну, ты сказал:)))
Описания осьмерочного языка под рукой нет.
Устроит в семерке обход дерева, где корень и ветви имеют тип СписокЗначений, а листья - другой тип?
33. Ярослав Волохов (YVolohov) 30.06.09 16:22
(32) устроит, только вот как в семерке можно реализовать дерево, там же такого объекта нет ?
34. Ярослав Волохов (YVolohov) 30.06.09 16:24
35. Евгений Люлюк (Evg-Lylyk) 30.06.09 16:28
(26) На чем тестил? А часто ли размер дерева известен? :)
(25) Не мерял, но почти уверен рекурсия будет эффективней
(28) "Значит первое мы определили, при прочих равных рекурсия затратнее цикла, надеюсь Вы согласитесь:-)" нет там совсем другой случай там рекурсия не нужна НА ПРИМЕРЕ АВТОРА ПОЖАЛУЙСТА

Для примера автора: рекурсию в 4 строки себе представляют все, а заменить рекурсию сложнее

Полный обход дерева каталогов как раз подходит для рекурсии
36. dushelov (Душелов) 30.06.09 16:33
"Лучше рекурсия чисто в эстетическом плане и в понимании кода, а фактически хуже (т.к. время на запись активации функции и размещения её на стэк всяка медленнее чем обычный jump). Т.к. для данной задачи производительность не критична, лично я голосую за рекурсию."

Взято отсюда: http://forum.codenet.ru/showthread.php?t=31862
37. Ярослав Волохов (YVolohov) 30.06.09 16:35
(35) тестил на http://www.infostart.ru/projects/4059/
в текущей версии 2.3 используется рекурсия,
в более старой версии 2.1 используется цикл,
дерево совершенно одинаковое (4 уровня, одинаковое количество элементов), тестил на одной и той же базе, на одном и том же компьютере
38. Александр Рытов (Арчибальд) 30.06.09 16:42
(33) В семерке есть все:)))

//Корень - это и есть корень
ТекСписок=СоздатьОбъект("СписокЗначений");
СледСписок=СоздатьОбъект("СписокЗначений");
ТекСписок.ДобавитьЗначение(Корень);
Пока ТекСписок.ДлинаСписка()<>0 Цикл
Для й=1 по ТекСписок.ДлинаСписка() Цикл
Ссылка=ТекСписок.ПолучитьЗначение(й);
Если ТипЗначенияСтр(Ссылка)<>"СписокЗначений" Тогда
//Это лист. Делаем с ним, что хотим, типа стамим пометку
Иначе //Это ветка. Вносим в список след. уровня
СледСписок.ДобавитьЗначение(Ссылка);
КонецЕсли;
КонецЦикла;
ТекСписок=СледСписок;
СледСписок=СоздатьОбъект("СписокЗначений");
КонецЦикла;
39. dushelov (Душелов) 30.06.09 16:44
(0) И конструкцию "Для Каждого ... Из ..." заменить на "Для ... По ...".
Это даст хороший прирост скорости.
40. Александр Рытов (Арчибальд) 30.06.09 16:45
41. Сергей Лунев (luns) 30.06.09 16:50
Все это ерунда.
Конструкции типа:
Код
Процедура ИзменитьПометкиПодчиненных(пГлавный)

    Подчиненные1 = пГлавный.Строки;
    Если Подчиненные1.Количество() = 0 Тогда
        Возврат;
    КонецЕсли;

    // Первый уровень подчиненных
    Для Каждого Подчиненный1 Из Подчиненные1 Цикл
        Подчиненный1.Пометка = пГлавный.Пометка;
        Подчиненные2 = Подчиненный1.Строки;
        Если Подчиненные2.Количество() = 0 Тогда
            Продолжить;
        КонецЕсли;

        // Второй уровень подчиненных
        Для Каждого Подчиненный2 Из Подчиненные2 Цикл
            Подчиненный2.Пометка = пГлавный.Пометка;
            Подчиненные3 = Подчиненный2.Строки;
            Если Подчиненные3.Количество() = 0 Тогда
                Продолжить;
            КонецЕсли;

            // Третий уровень подчиненных
            Для Каждого Подчиненный3 Из Подчиненные3 Цикл
                Подчиненный3.Пометка = пГлавный.Пометка;
            КонецЦикла;
        КонецЦикла;
    КонецЦикла;
КонецПроцедуры
Показать полностью


Непонятны и трудночитаемы. Выйгрыш на дереве в 4-5 вложенности будет минимальным, при вложенности 1000 страшно представить себе этот код.

Во общем наш выбор: рекурсия!
42. Александр Рытов (Арчибальд) 30.06.09 16:53
(41) См. пост 36. И 39 тоже.
Кодеры, блин...
43. Ярослав Волохов (YVolohov) 30.06.09 16:56
(39) надо будет попробовать
(40) дерево значений созданное из списков значений рулит однозначно ))), семерка действительно может все )))
Арчибальд; +1 Ответить
44. Сергей Лунев (luns) 30.06.09 16:57
(42) И что? Можете пример для 30 уровней вложенности привести?
Выигрыш в долю микросекунды на маленьком дереве меня не интересует, если придется потратить десятки минут на то чтобы разобраться в 100 там, где достаточно 10.
45. Сергей Лунев (luns) 30.06.09 16:58
в 100 строчка кода имелось ввиду.
46. Евгений Люлюк (Evg-Lylyk) 30.06.09 17:00
Давайте исходит из примера автора т.к. для 90% приведенных случаев рекурсия не нужна в том числе и в варианте форума от Душелова. Я чуток знаю низкий уровень (assembler) вызов функции это очень мало операций
push АдресВозврата;
push ПеременнаяХ;
Jmp АдресПроцедуры;
+
Внутри процедуры
Одно вычитание (сдвиг стека)
и возврат

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

(37) а что делать если число уровней неизвестно
47. Александр Рытов (Арчибальд) 30.06.09 17:02
(44,45) Я ж и привел в 25 и 38. Количество уровней не лимитировано. А авторский текст, процитированный в (41) - жесть, что я попытался выразить в 42 посте...

ВоооООтоЧемрееееЕчь...
48. Ярослав Волохов (YVolohov) 30.06.09 17:04
(44) в приведенном примере всего 4 уровня, причем в http://infostart.ru/projects/4059/ где изначально использовалась процедура из (41) размер дерева и структура фиксированы (корень, коллекции, объекты, таблицы). Если дерево больше, я согласен что надо использовать рекурсию. Да собственно и в этом примере она целесообразнее. Но если дерево небольшое, и размер его фиксирован, то не принципиально что использовать.
49. Евгений Люлюк (Evg-Lylyk) 30.06.09 17:09
Речь о том что рекурсия эффективней в тех случаях когда она реально необходима, пример полный обход дерева каталогов диска
Преимущество рекурсии: читабельность, модифицируемость, разница в скорости ничтожна и в большинстве случаев влияют другие факторы
50. dushelov (Душелов) 30.06.09 17:13
Что пишет MSDN:

Рекурсивные процедуры

Рекурсивная процедура — это процедура, которая вызывает сама себя. Как правило, это не самый эффективный способ написания кода.


**** Рассмотрение рекурсивных процедур

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

- Использование памяти.
Приложение имеет ограниченный объем пространства для локальных переменных. Каждый раз, когда процедура вызывает саму себя, она использует больше этого пространства для дополнительных копий ее локальных переменных. Если этот процесс будет продолжаться неопределенно долго, он в конечном счете вызовет ошибку StackOverflowException.

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

- Взаимная рекурсия.
Можно наблюдать очень низкую производительность или даже бесконечный цикл, если две процедуры вызывают друг друга. Такой макет представляет те же проблемы, что и одна рекурсивная процедура, но это может быть сложнее обнаружить и отладить.

- Тестирование.
Если Вы пишете рекурсивную процедуру, необходимо проверить ее очень внимательно, чтобы убедиться в в том, что она всегда удовлетворяет некоторому граничному условию. Следует также убедиться в том, что в результате слишком большого количества рекурсивных вызовов вы не израсходуете всю доступную память.
51. dushelov (Душелов) 30.06.09 17:18
Вопрос:
- Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует памяти, линейно возрастающей с вызовом процедур? Насколько я понимаю, в момент вызова процедуры в стек помещаются параметры процедуры. А если их нет? Адрес возврата?

Ответ:
- Да. Так или иначе запоминается адрес возврата.
Локальные переменные ещё.

Взято тут: http://www.rsdn.ru/forum/decl/2905355.flat.aspx
52. Александр Рытов (Арчибальд) 30.06.09 17:18
(49) Набор "последовательность+Ветвление+цикл" является ДОСТАТОЧНЫМ для любого алгоритма. Это постулат. Поэтому случаев, когда рекурсия НЕОБХОДИМА просто не существует. Другое дело, что рекурсия зачастую элегантней выглядит...
53. dushelov (Душелов) 30.06.09 17:25
(52) В ряде случаев рекурсия бывает выгоднее.

http://www.intuit.ru/department/pl/csharp/10/3.html

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

В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие - кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.

Беспокоиться о близком конце света не стоит. Задача эта не под силу и современным компьютерам. Число ходов в ней равно 264, а это, как известно, большое число, и компьютер, работающий в сотню миллионов раз быстрее монахов, не справится с этой задачей в ближайшие тысячелетия.

....

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

....

Можно показать, что последовательность ходов, реализуемая рекурсивным алгоритмом, является оптимальной, так что никакой другой алгоритм не может решить задачу за меньшее число ходов.
54. Евгений Люлюк (Evg-Lylyk) 30.06.09 17:29
Согласен с рекомендациями, но сам знаешь что есть случаи когда рекурсия лучший выбор, пример полный обхода дерева. А все эти факторы влияют по разному в разных случаях гдето например "эффективность использования памяти" сходит на нет.
55. Александр Рытов (Арчибальд) 30.06.09 17:30
56. Ярослав Волохов (YVolohov) 30.06.09 17:31
Итак к чему мы пришли:

вариант приведенный в (41) основан на циклах, выполняется быстрее рекурсии, но не подходит для слишком больших деревьев или деревьев с неизвестным количеством уровней;

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

вариант предложенный Арчибальдом, построен на циклах, поэтому не имеет недостатков рекурсии, подходит для деревьев любого размера, но код его менее читабельный чем рекурсия, к тому же требует адаптации к 8-ке.
57. Александр Рытов (Арчибальд) 30.06.09 17:37
(53)Там, главное, не перепутать (чтобы кольца в конце оказались на второй, а не на третьей пирамиде). Поэтому цепочку действий оптимальнее "раскручивать" с конца, т.е. рекурсивно. Без рекурсии мы вынуждены работать с начала...
58. Дмитрий Трапезников (trad) 30.06.09 18:10
Тема безрекурсивного вывода дерева ФС не раскрыта.

ps
Если что, то под древовидным выводом я понимаю такой вывод в котором видна родственная связь элементов
59. Александр Рытов (Арчибальд) 30.06.09 18:13
(58) Рекурсивного вывода, кстати, тоже...
60. Евгений Люлюк (Evg-Lylyk) 30.06.09 18:37
(56) Осталось только все выводы учесть в шапке статьи как оказалось все не однозначно :)))
Кстати про недостаток рекурсии "переполнение стека" это происходит при большом уровне вложенности что крайне редко. ИМХО "замены" потребляют не меньше памяти
61. Ярослав Волохов (YVolohov) 30.06.09 18:41
(60) Адаптирую вариант Арчибальда под 8-ку (если получиться), сделаю замеры производительности по всех вариантах, вот тогда и допишу концовку статьи со сравнением. А пока еще не все ясно.
Evg-Lylyk; +1 Ответить
62. Дмитрий Трапезников (trad) 30.06.09 19:00
(59)
Перем гТекст;

Процедура ВывестиПодчиненные(Каталог, Отступ="")
Перем Атрибуты;
Состояние(Каталог);

_ФС = СоздатьОбъект("ФС");
ИмяФайла = _ФС.НайтиПервыйФайл(Каталог+"*");
Пока ПустаяСтрока(ИмяФайла) = 0 Цикл

Если Лев(ИмяФайла, 1) <> "." Тогда
гТекст.ДобавитьСтроку(Отступ+ИмяФайла);
_ФС.АтрибутыФайла(Каталог+ИмяФайла,,Атрибуты);
Если Сред(Атрибуты, 4, 1) = "1" Тогда
ВывестиПодчиненные(Каталог+ИмяФайла+"\", Отступ+" ");
КонецЕсли;
КонецЕсли;

ИмяФайла = _ФС.НайтиСледующийФайл();
КонецЦикла;
КонецПроцедуры

Процедура Сформировать()
гТекст = СоздатьОбъект("Текст");
ВывестиПодчиненные("C:\");
гТекст.Показать("C:");
КонецПроцедуры
63. Дмитрий Трапезников (trad) 30.06.09 19:01
64. Евгений Люлюк (Evg-Lylyk) 30.06.09 21:35
На 8-ке:

Процедура КнопкаВыполнитьНажатие(Кнопка)
ОбходДереваКаталоговРекурсия("D:\DISTRIB\")
КонецПроцедуры

Процедура ОбходДереваКаталоговРекурсия(Каталог)

НайдФайлы = НайтиФайлы(Каталог,"*.*");
Для Каждого Файл Из НайдФайлы Цикл
Состояние (Файл.ПолноеИмя);
Если Файл.ЭтоКаталог() Тогда
ОбходДереваКаталоговРекурсия(Файл.ПолноеИмя);
КонецЕсли;
КонецЦикла;

КонецПроцедуры


Вместо "Состояние (Файл.ПолноеИмя);" можно вставить любой код
65. Александр Рытов (Арчибальд) 01.07.09 07:35
(63) Да не интересно мне. Ясно же, что решаемо, и достаточно просто.

66. Александр Орефков (orefkov) 01.07.09 11:35
В цикл преобразуется только хвостовая рекурсия.
Остальные виды рекурсий в общем виде пробразуются в "цикл + стек".
Рассматривая языки более приближенные к процессору, чем 1С (такие как С / С++), стоит отметить, что организация стека при рекурсивном вызове заключается лишь в изменении стекового регистра. А вот организация объекта-стека при безрекурсивном цикле может быть довольно-таки сложна и включать в себя работу с динамической памятью (выделение/перевыделение), копировании объектов в стек и обратно и тп. Так что имхо на С и С++ для нетривиальных рекурсий довольно неплохие шансы побить их безрекурсивные аналоги.
67. Евгений Люлюк (Evg-Lylyk) 01.07.09 12:10
(0) комментарии к последнему выводу
"Перейдем к недостаткам. Использование рекурсии с большой глубиной может привести к переполнению стека и ошибке в работе программы. В случае использования рекурсии быстродействие программы уменьшается сравнительно с использованием циклов. Следовательно, если количество уровней вложенности дерева относительно небольшое, а количество строк большое, то целесообразнее использовать циклы."
Неверный вывод. Для большой глубины замены рекурии будут также переполнять память.
"Следовательно, если количество уровней вложенности дерева относительно небольшое, а количество строк большое, то целесообразнее использовать циклы". Один из недостатков рекурсии доп. вызов функции, но он производится только при шаге в глубь.

(66) да и зачем реализовывать тоже самое что уже реализовано внутри "call" (вызова процедуры)
68. Ярослав Волохов (YVolohov) 01.07.09 12:20
Обновил статью, добавил в начало несколько простых примеров для лучшего понимания, провел тестирование производительности и получил определенные выводы.

В общем для деревьев с большим количеством строк и малым количеством уровней оптимальнее использовать циклы. Выигрыш в быстродействии.

Для деревьев с малым количеством строк и большим количеством уровней оптимальнее использовать рекурсию. Выигрыш в читабельности и размере кода.

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

Для деревьев с малым количеством строк и малым количеством уровней нет разницы что использовать.

Для деревьев с неизвестным заранее количеством уровней можно только использовать рекурсию.
69. Евгений Люлюк (Evg-Lylyk) 01.07.09 12:35
(68) можно увидеть примеры на которых вы тестировали т.к. я в них сомневаюсь если это "ВывестиЧисла(пЧисло)" то тогда понятно.
Для тех случаев когда рекурсия необходима она не имеет значительной потери в скорости, а должна даже выигрывать и неважно сколько в дереве уровней и строка рекурсия будет эффективной.
Еще пример для рекурсии расчет выражений например:
"С=A+B; A=10; B=A+7"

Для обхода дерева с неограниченным количеством уровней как в твоем примере для 8.х никто не привел пример. Как мне кажется я потрачу на это больше часа и точно не будет быстрее твоего варианта.
А пример 38 омеет очень много операций он не будет быстрым

70. Ярослав Волохов (YVolohov) 01.07.09 12:41
В конце статьи есть ссылка на обработку на которой я тестировал. Дерево небольшое, около 1000 строк, 4 уровня. Можешь сам попробовать. Там просто нужно заменить процедуру ИзменитьПометкиПодчиненных() на один а затем на другой вариант и посмотреть что будет быстрее. А насчет вывода чисел - так это только пример, для лучшего понимания, практического значения он не имеет.
71. Ярослав Волохов (YVolohov) 01.07.09 12:49
(70) около 1000 строк было на той конфигурации, на которой я тестировал, на других может быть и больше (в зависимости от количества метаданных и таблиц)
72. Евгений Люлюк (Evg-Lylyk) 01.07.09 13:56
(71) Проверил. Для замены на 4 ре цикла рекурсия медленне на 30-50%. Это проблема 1С т.к. в любом "нормальном" языке программирования операция установки пометки будет в десятки раз дольше вызова функции. Можно написать что для известного числа уровней цикл быстрее на Х %. Но нужно не забывать о читаемости т.к. на 30000 строк (я просто запустил 10 раз) на моем компе ушло 1,2 сек на рекурсию и 0.89 на циклы.
Опять же если говорить о неизвестном размере дерева (как часто бывает) вопрос открытый.
73. Ярослав Волохов (YVolohov) 01.07.09 14:13
(72) а есть ли зависимость между количеством уровней дерева и быстодействием, или например между количеством строк и быстродействием ? Тоже вопрос открытый.
74. Ярослав Волохов (YVolohov) 01.07.09 14:16
(72) пожалуй что наиболее доступное дерево с неизвестным заведомо размером это файловая система
75. Александр Венгер (venger) 01.07.09 19:28
Н-да.... Ну ладно, похоже Вы вдовоем друг друга (YVolohov, Evg-Lylyk) уговорите в верности чего угодно:-))) Ну да ладно.... Если Вам интересно и приятно, то почему бы и нет:-)
76. Ярослав Волохов (YVolohov) 01.07.09 19:48
(75) Человек старался, тестировал, пришел к определенным выводам, причем достаточно интересным. Почему он не заслуживает плюсика?
77. Александр Венгер (venger) 01.07.09 20:12
(76) Вы в этом плане молодец, я не спорю. Но выводы, т.е. ИМХО, чуть позже и плюс тоже, хорошо? А пока я на море ополоснусться (мне пять минут ходу):-)
78. Евгений Люлюк (Evg-Lylyk) 02.07.09 09:25
(75) Если что то неверно расскажи. А мне плюсов не жалко у меня их много :)))
79. Александр Рытов (Арчибальд) 02.07.09 10:01
(68)
> Для деревьев с неизвестным заранее количеством уровней можно только использовать рекурсию.

Автор с упорством, достойным лучшего применения, отрицает очевидное. Приведен же ясный пример в 11 строк обхода произвольного дерева.
80. Александр Рытов (Арчибальд) 02.07.09 10:05
+79 О как! Оказывается и в самой статье появился вывод о неизбежности рекурсии. Это уже прямая ложь, заслуживающая жирного минуса...

ТаааАквоооОоот...
81. Ярослав Волохов (YVolohov) 02.07.09 10:59
(79) (80) Публично покаюсь, если сможешь применить этот код к восьмерочному дереву. Лично у меня не получилось.
82. Александр Рытов (Арчибальд) 02.07.09 11:44
(81)К дереву на Лиспе код тоже не применим. Код опровергает утверждение статьи, цитирую
" Подведем итоги. В результате этого небольшого исследования мы выяснили, что рекурсию целесообразно использовать для работы с деревьями, имеющими большое количество уровней вложенности или деревьями, количество уровней вложенности которых не определено. В последнем случае применение рекурсии – ЕДИНСТВЕННО возможный механизм."
По поводу восьмерки. Вы хотите заявить, что восьмерка не позволяет создать ссылку на элемент (ветку) дерева? Или, что приведенный мной алгоритм неуниверсален (годится не для всяких деревьев)? Или, что дерево в восьмерке не такое как все?

83. Ярослав Волохов (YVolohov) 02.07.09 12:24
//*******************************************
Процедура Сформировать()

Корень = СоздатьОбъект("СписокЗначений");
Ветка1 = СоздатьОбъект("СписокЗначений");
Ветка2 = СоздатьОбъект("СписокЗначений");
Для Счетчик = 1 По 10 Цикл
Корень.ДобавитьЗначение(1);
Ветка1.ДобавитьЗначение(11);
Ветка2.ДобавитьЗначение(12);
КонецЦикла;
Корень.УстановитьЗначение(4,Ветка1);
Корень.УстановитьЗначение(6,Ветка2);

//Корень - это и есть корень
ТекСписок=СоздатьОбъект("СписокЗначений");
СледСписок=СоздатьОбъект("СписокЗначений");
ТекСписок.ДобавитьЗначение(Корень);
Пока ТекСписок.РазмерСписка()<>0 Цикл
Для й=1 по ТекСписок.РазмерСписка() Цикл
Ссылка=ТекСписок.ПолучитьЗначение(й);
Если ТипЗначенияСтр(Ссылка)<>"СписокЗначений" Тогда
Сообщить(Строка(Ссылка));
Иначе //Это ветка. Вносим в список след. уровня
СледСписок.ДобавитьЗначение(Ссылка);
КонецЕсли;
КонецЦикла;
ТекСписок=СледСписок;
СледСписок=СоздатьОбъект("СписокЗначений");
КонецЦикла;
КонецПроцедуры

Вот твой алгоритм на семерке вместе с небольшим деревом, которое он должен просто обойти. При попытке его использовать компьютер просто зависает. Дерево очень простое - корень и две ветки.
84. Ярослав Волохов (YVolohov) 02.07.09 12:27
Протестируй сам. Да, еще функцию ДлинаСписка я заменил на РазмерСписка, а то выбрасывало ошибку, а больше я ничего не менял.
Арчибальд; +1 Ответить
85. Александр Рытов (Арчибальд) 02.07.09 13:29
(83) Ну, конечно. По Иначе нужно в СледСписок заносить не сам список, а его элементы

Для йй=1 по Ссылка.РазмерСписка() Цикл
СледСписок.ДобавитьЗначение(Ссылка.ПолучитьЗначение(йй));
КонецЦикла;

Прошу пардону. Но минус не сниму.
86. Александр Рытов (Арчибальд) 02.07.09 13:33
А вот плюсик за тестирование выдам...
87. Ярослав Волохов (YVolohov) 02.07.09 13:59
(85) Вот сейчас действительно заработало ))) Дерево обходит полностью, правда порядок обхода несколько другой чем у рекурсии или циклов.
Если корень дерева отметить как 1, подчиненные второго уровня как 11, 12, 13, 14 , третьего уровня 111, 112, 113, 114 и т. д. то цикл или рекурсия обходят так:
1 - 11 - 111 - 112 -113 -114 -12 - 112 - 113 - 114 а этот алгоритм так -
1 - 11 - 12 - 13 - 14 - 111 - 112 -113 - 114 - 121 - 122 - 123 и т.д.

Но это не играет особенной роли, если потомок не должен наследовать каких-либо свойств именно от своего предка. При установке или снятии пометки такого не требуется, поскольку все потомки наследуют свойство (состояние пометки) от общего предка (корня). Так что ты прав - альтернативный рекурсии алгоритм существует.
88. Ярослав Волохов (YVolohov) 02.07.09 14:02
Сейчас попробую сделать то же для восьмерки.
89. Александр Рытов (Арчибальд) 02.07.09 14:07
(87)Ну да, рекурсия по каждой ветке лезет до листьев, а здесь каждый уровень последовательно обходится. Кстати, номер уровня можно фиксировать и записывать свойство, зависящее и от корневого значения, и от номера уровня.
При рекурсии труднее иметь номер уровня под рукой :))
90. Ярослав Волохов (YVolohov) 02.07.09 14:38
Процедура ИзменитьПометкиПодчиненных(пГлавный)
СтрокиДереваА = Новый Массив;
СтрокиДереваБ = Новый Массив;
СтрокиДереваА.Добавить(пГлавный);
Пока НЕ (СтрокиДереваА.Количество() = 0) Цикл
Для Каждого СтрокаДерева Из СтрокиДереваА Цикл
СтрокаДерева.Пометка = пГлавный.Пометка;
Для Каждого СтрокаДереваПодчиненная из СтрокаДерева.Строки Цикл
СтрокиДереваБ.Добавить(СтрокаДереваПодчиненная);
КонецЦикла;
КонецЦикла;
СтрокиДереваА = СтрокиДереваБ;
СтрокиДереваБ = Новый Массив;
КонецЦикла;
КонецПроцедуры

А вот и код на восьмерке, все работает, проверял. Не знаю только как это будет выглядеть с позиций быстродействия, нужно будет протестировать.
91. Александр Венгер (venger) 02.07.09 14:48
Просто пару уточнений по статье:

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

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

Пока 1=1 Цикл
КонецЦикла;

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

Нет таких задач, чтобы невозможно. А вот целесообразно, пока видел только пример про Ханойские башни.

"Если максимальное количество уровней дерева неизвестно или так велико, что использовать вложенные циклы просто неэффективно, код получиться слишком громоздкий, да еще и повторяющийся?"

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

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

А по поводу читабельности и более легкого понимания рекурсии.
Вы пробовали простому пользователю (желательно не шибко умному и не шибко математичному) объяснить циклы, а потом рекурсию? Как думаете, что он быстрее поймет? Да и со студентами также. Циклы сразу понятны, а рекурсия не сразу всем доступна и понятна становится.... Она тяжелей воспринимается в среднем обущающимися, чем понятие цикла...
92. Ярослав Волохов (YVolohov) 02.07.09 16:02
Ну насчет бесконечного цикла или рекурсии то это не принципиально, можно сказать "бесконечное повторение одного фрагмента кода", суть от этого не меняется.

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

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

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

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

Насчет понимаемости рекурсии то тут я согласен. Циклы понять легче. А вот читабельность кода - другое дело. Сравните размеры последней и предпоследней процедуры в статье.
93. Александр Венгер (venger) 02.07.09 16:25
(92) > Насчет громоздкости кода - попробуйте себе представить код с девятнадцатью вложенными циклами (для обхода двадцатиуровневого дерева).

Вы так и не поняли, что 19-ть вложенных циклов делать не нужно;-)
Остальные Ваши возражения, что принципиально, что нет, по другим уточнениям из поста 91-го тоже вызывают улыбку;-)

Н-да, похоже действительно спорить с Вами бесполезно;-) Сорри, но со статьей не согласен, пока минус...
94. Ярослав Волохов (YVolohov) 02.07.09 16:37
А я и не говорю что обязательно нужно делать 19 вложенных циклов и что это единственный выход, посмотрите лучше (90). Несколько вложенных циклов это один из выходов, подходящий для деревьев с небольшим количеством уровней и большим количеством элементов.
А улыбка это хорошо, полезно для здоровья. )))
Арчибальд; +1 Ответить 1
95. Александр Рытов (Арчибальд) 02.07.09 16:57
(94)На мой вкус, Вы еще плюс заработали. За то, что спор не перерос в скандал. Вообще-то это подразумевается, но пока, к сожалению, проблематично.
А за статью минус оставляю.
96. Ярослав Волохов (YVolohov) 02.07.09 17:03
Спасибо за поддержку. Скандалить в любом случае не буду, разве что нарвусь на откровенное хамство )))
А статью я еще доделаю. В итоге должны быть описаны все возможные варианты решения проблемы.
97. Александр Венгер (venger) 02.07.09 21:12
(96) > разве что нарвусь на откровенное хамство

А что скандалить, да я понимаю, что рекурсия красиво выглядит и сам через такое проходил, очень не хотелось отказываться от нее во многих случаях, вот и Вы ищете чем оправдать (я тоже с большим "не удовольствием" принял этот факт), но факт остается фактом, я с самого начала в первых постах все сказал...

По этому поводу есть анекдот:
Программа по заявкам по кацапскому радио:
"Пишет нам ученик 9го класса с.ш. г. Ленинграда Вася Пупкин и просит поставить для него песню "Валенки" в исполнении Руслановой-пожалуйста"
Прошло 5 лет, та же передача:
"Пишет нам студент Вася Пупкин - песню " Валенки " в исп. Руслановой - слушайте".
Прошло 20 лет, та же передача:
"Пишет нам директор предприятия Василий Васильевич Пупкин и просит поставитть Фугу ля минор И-С. Баха. Василий Васильевич не вые@ывайтесь и слушайте свои "Валенки".

Мораль такова, что иногда нет смысла выпендриваться - только хуже будет:-)
98. Евгений Люлюк (Evg-Lylyk) 03.07.09 02:03
(97) На мой взгляд выпендривание это как раз замена рекурсии, я про случай с обходом дерева. Согласен что рекурсию понять сложнее чем цикл, но когда понимаешь используешь только ее т.к. на самом деле в определенных случаях это более читабельный вариант
(90) проверьте пожалуйста быстродействие в сравнении с рекурсией, а то тут многие видят это как "эффективную" :)замену рекурсии. Не знаю как студенты, но мне честно трудно понять что там делается.

99. Евгений Люлюк (Evg-Lylyk) 03.07.09 02:07
(89) "При рекурсии труднее иметь номер уровня под рукой :))" легко перед вызовом процедуры рекурсии увеличить счетчик и его передать в процедуру... все..
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа