Всем доброго дня.
Есть дерево

Строка 1(Уровень1)
+Строка 11 (Уровень2)
+Строка 12 (Уровень2)
  ++Строка 121 (Уровень3)
  ++Строка 122 (Уровень3)
Строка 2 (Уровень1)
+Строка 21(Уровень2)
..................

Как получить в таком случае максимальный уровень?

(0) Открыть для себя рекурсивные методы обхода дерева

в каком таком?
если родитель = неопределено тогда
уровень = макимальный

(2) Не думаю, что все так просто)

(1)+

(3) все именно настолько просто.

ответ на (0) должен быть 3?

Дерево можно и без рекурсии обходить.
Просто массив того,что еще нужно обойти сделать.

(7) перебор с возвратом предлагаешь?

(7) Причем необходимо этот массив для имитации стека эмулировать на регистре расчета.

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

(10) > просто,быстро

А. Ну то есть при использовании рекурсии надо просто отработать дочерние, а при использовании массива - надо запомнить директорию в массиве... и отработать дочерние.

Да, действительно, это проще.

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

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

(12) > в одном иттераторе.
///////////////////////////////////////////////////////////////////////////////////

Процедура ОпределитьМаксимальныйУровень(Строки, Уровень, МаксимальныйУровень)

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

МаксимальныйУровень = 1;
ОпределитьМаксимальныйУровень(Дерево.Строки, 0, МаксимальныйУровень);
Сообщить(МаксимальныйУровень);

///////////////////////////////////////////////////////////////////////////////////

Давай свое "проще"

(14) Мне досталось однажды тестовое задание - обход дерева без рекурсии. При изучении(решении этого вопроса (ну-да, вот такой 1с-ник) неожиданно узнал,что рекурсия - это зло в программировании, а нормальные, достойные прогеры делают всё через циклы. Так может быть здесь тот случай?

(14) если макс уровень под тыщу будет, то может глубины стека не хватить

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

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

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

(18) > Берем массив,в который
Код напиши и выложи. Сравним про "просто" и "быстро"

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

(20) Пора начинать как в политике пруфы требовать =)

(21) а, нет, это в учебнике по Паскалю было для школьников

Д. Баррон, Рекурсивные методы в программировании, Москва, 1974 год:

Существует мнение, что "если бы в средние века были вычислительные машины, то одни программисты сжигали бы на кострах других программистов за ересь". Почти наверняка самой страшной ересью считалась бы вера (или неверие) в рекурсию. Достоинства и недостатки рекурсии как средства программирования подвергались широкому обсуждению в течение последних нескольких лет. Как нередко бывает в таких ситуациях, имеется тенденция к сохранению крайних взглядов и к рассмотрению проблемы либо в черном, либо в розовом свете. Одни утверждают, что всегда лучше пользоваться не рекурсией, а итерацией. Другие же настолько верят в рекурсию, что они не снисходят до включения очевидных методов итерации в разрабатываемые ими языки программирования. Автор придерживался при написании этой книги промежуточной позиции, избегая крайних точек зрения. По возможности предмет излагается с учетом перспектив, демонстрируются способы успешного применения рекурсии в различных ситуациях, выявляются соотношения между рекурсией и более известными итеративными методами.


Дейкстра, ага...

(23) Вот видишь, и Баррон тоже пишет что мол "существует менение". А мнение он это прочитал наверное на Хабре

Когда стек из 16 вызовов,как на встраиваемых системах,то о рекурсии приходится забыть.

Процедура ОбойдиДерево(СтрокиДереваЗначений)
Массив=Новый Массив
Массив.Добавить(СтрокиДереваЗначений)
ПозицияМассива=1
Пока ПозицияМассива>0 Цикл
  ПозицияМассива=ПозицияМассива-1
  СтрокиДляОбхода=Массив.Получить(ПозицияМассива)
  Для Каждого СтрокаДерева Из СтрокиДляОбхода Цикл
   Если ПозицияМассива<Массив.Количество()Тогда
    Массив[ПозицияМассива]=СтрокаДерева.Строки
   Иначе
    Массив.Добавить(СтрокаДерева.Строки)
   КонецЕсли
   ПозицияМассива=ПозицияМассива+1
  КонецЦикла
КонецЦикла
Сообщить("ГлубинаДерева:"+Строка(Массив.Количество()))
КонецПроцедуры

Ну да, ну да. Одеваем лыжи и лезем в гамак, утешая себя, что это встраиваемая система.
Получается "проще" и "понятней". По поводу "быстрее" - медленней на 2%.
Ну и прочее там, перевыделение памяти под новые элементы массива вообще тихо стороной обошел.

А почему, кстати, при обсуждении того, какое ООП мимими и очень плохо, что его в 1С нет, никто не считает расход памяти под таблицы виртуальных методов, например?

(24) > на Хабре
Не прочитал, а написал уж тогда. Положил в чулан в 1974 году, подождал когда напишут 1С и вот, опубликовал.

(14) любая рекурсия может быть обыграна циклом... экономичнее по ресурсам, чуть быстрее но чуть сложнее.

(28) >  экономичнее по ресурсам,
Сильно зависит от реализации. При отсутствии локльных переменных метода и общей памятью под стек и данные - равнозначно.

> чуть быстрее
Вообще не факт. Приведенный пример проигрывает на два процента:
Уровень1 = Тест1(Дерево);               10 000    1,869380    48,73
Уровень2 = ОбойдиДерево(Дерево.Строки); 10 000    1,952564    50,89

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

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

Уже две недели обхожу дерево двумя циклами: на первом уровне Заказы покупателей, на втором уровне Номенклатура Заказов. ЧЯДНТ?

(30) у тебя слишком "низкое" дерево

(29) лень, но завтра проверю, на 8.2.13 было чуть быстрее... ну и да, гарантированно нет стековерфлова

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

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

И опять же sax-parser на цикле выглядит более понятно,чем на рекурсии.

(32) > на 8.2.13 было чуть быстрее
Ну вот, слишком много зависимостей от реализации. Я замеры на 8.3.20.1674 делал.

(34) > ничего не мешает выделять ее блоками,просто,1с так не умеет,
И опять - слишком много зависимостей от реализации.

(33) > параллельных обращений к файловой системе.
А откуда у тебя "параллельные обращения" вообще взялись?

Хотя,в принципе,одинаково:
Функция ПолучитьСписокФайловВДиректории(Директория)
...
КонецФункции

Функция ОбработатьФайл(ИмяФайла,Параметры)
...
КонецФункции

//Рекурсия
Процедура ОбработатьФайлыРекурсия(Директория,Параметры)
СписокФайлов=ПолучитьСписокФайловВДиректории(Директория)
Для Каждого Файл Из СписокФайлов Цикл
  Если ЭтоДиректория(Файл) Тогда
   ОбработатьФайлыРекурсия(Файл,Параметры)
  Иначе
   ОбработатьФайл(Файл,Параметры)
  КонецЕсли
КонецЦикла
КонецПроцедуры

//Цикл
Процедура ОбработатьФайлыЦикл(Директория,Параметры)
МассивОбхода=Новый Массив()
МассивОбхода.Добавить(Директория)
ПозицияВставки=1
Пока ПозицияВставки>0 Цикл
  ПозицияВставки=ПозицияВставки-1
  ТекущаяДиректория=МассивОбхода[ПозицияВставки]
  МассивФайлов=ПолучитьСписокФайловВДиректории(ТекущаяДиректория)
  Для Каждого Файл Из СписокФайлов Цикл
   Если ЭтоДиректория(Файл)Тогда
    Если МассивОбхода.Количество()>ПозицияВставки Тогда
     МассивОбхода[ПозицияВставки]=Файл
    Иначе
     МассивОбхода.Добавить(Файл)
    КонецЕсли
    ПозицияВставки=ПозицияВставки+1
   Иначе
    ОбработатьФайл(Файл,Параметры)
   КонецЕсли
  КонецЦикла
КонецЦикла
КонецФункции

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

(34) "ничего не мешает выделять ее блоками,просто,1с так не умеет,в отдичие от других языков где это очень просто. "

А что еще вы знаете про менеджер памяти 1С?

Память везде выделяется блоками по 64 Кб, это уровень системы, другой вопрос, что менеджер памяти потом с ней делает:

https://www.transl-gunsmoker.ru/2008/11/64.html

(40) как это везде? а как-же alloc/malloc?

Страница,обычно 4kb,а не 64.
И потом,выделение памяти процессу от системы и выделение памяти из кучи,которая сама по себе у системы выделена - это разные вещи.
Опять же,под массив и другие структуры 1с изначально выделяет память,включающую небольшое число элементов,так как стараются под все объекты ввделять блоки одинакового размера - это не приводит к фрагментации,а потом выделяется память под дополнительные элементы.
Опять же,команда Массив.Добавить не обязательно ввделяет память,а только сдвигает указатель используемого места.

в массиве же сразу можно задать количество элементов

(42) > это не приводит к фрагментации
Фантазии, фантазии... На линуксе раньше вообще треш творился, они даже рекомендовали дополнительно TCmalloc ставить.

> не обязательно ввделяет память
А когда выделяет, забирает с запасом, с коэффициентом 1.5. Про это даже в Космосе рассказывали.

(43) Да можно конечно. Причем оптимально - сразу равным максимальной глубине вложенности дерева, которое нам надо посчитать =)

(14) Вместо процедуры нарисовать функцию.
Сообщить( МаксимальныйУровень(Дерево.Строки, 0) );

Функция после выхода память освобождает?

А кто вообще решил, что стек где-то переполняться будет?

Вызов превращается примерно в:
PUSH параметры, при этом в случае с деревом передается адрес, а не само дерево
Далее CALL это по сути PUSH адрес возврата и JMP.
При возврате происходит обратное чтение из стека и стек освобождается.

Т.е. стек занимается по сути максимально = Макс Количество Уровней вложенности * объем передаваемых параметров. Это же пшик.

(47) а ты попробуй... 8.2.13 валилась на вложенности порядка 5-5,5К (раз на раз не приходилось)

(47) 8.3.17 валится на 1200 вложенности
8.3.18 валится на 700 вложенности

Там же не только те параметры, которые ты указал, но и что-то внутреннее тянется.

(49) Угу. Там еще состояние локального контекста, локальные переменные, вот это все...

Сейчас посмотрел, файловая 8.3.20 валится на 650. Прогресс, однако.

У 1с виртуальная машина,так что там не только CALL,но и выделение области под данные функции и это не javascript,где параметры отдельно.

(51) "под данные функции" - какие данные у функции?
На входе ссылка на строки дерева значений и простое число. + обратная ссылка возврата из функции.

(25) мне просто впадлу столько строчек писать.
поэтому, даже не рассматриваю варианты без рекурсии. может не прав. мне фиолетово.

Из (14) там нет каких-то переменных с данными.

Функция МаксимальныйУровень(Строки, ТекУровень, МаксимальныйУровень)
    ПЕРЕМ СтрокаДЗ; // Это просто ссылка

    Если Строки.Количество() = 0 Тогда
        Возврат Макс(МаксимальныйУровень, ТекУровень);
    КонецЕсли;

    Для Каждого СтрокаДЗ Из Строки Цикл
        МаксимальныйУровень(СтрокаДЗ.Строки, ТекУровень + 1, МаксимальныйУровень)
    КонецЦикла;
    
КонецПроцедуры

Сообщить( МаксимальныйУровень(Дерево.Строки, 0, 0) );

+(53) да и не написал бы я так коротко, минимум в три раза больше строк. рекурсия для ленивых и слабых.

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

к (54)
Наверное вот так будет... Но не суть важно. Не понимаю где так много памяти надо?

Функция МаксимальныйУровень(Строки, ТекУровень, МаксимальныйУровень)
    ПЕРЕМ СтрокаДЗ;// Это просто ссылка

    Если Строки.Количество() = 0 Тогда
        Возврат Макс(МаксимальныйУровень, ТекУровень);
    КонецЕсли;

    Для Каждого СтрокаДЗ Из Строки Цикл
        МаксимальныйУровень = МаксимальныйУровень(СтрокаДЗ.Строки, ТекУровень + 1, МаксимальныйУровень)
    КонецЦикла;

    Возврат МаксимальныйУровень;
    
КонецПроцедуры

Сообщить( МаксимальныйУровень(Дерево.Строки, 0, 0) );