ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Рекурсия. Как правильно?
19 сообщений из 19, страница 1 из 1
Рекурсия. Как правильно?
    #37820823
enigmatic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
enigmatic
Участник
Имеется простейшая структура данных: дерево, где элемент имеет ссылку на родителя.
Нужна функция, определяющая, является ли один элемент дочерним для второго.

Пишу функцию, которая бы просто делала то, что мне нужно:
Пишу рекурсивную функцию следующим образом (мой код на C# просто потому что мне так удобнее):
Код: c#
1.
2.
3.
4.
5.
        public bool IsChildOf(ColumnViewTreeItem item) {
            if (Parent == null) return false;
            if (Parent == item || this == item) return true;
            return Parent.IsChildOf(item);
        }


Я вижу, что она может быть реализована лучше: здесь присутствует разлапистый if, неудобно определены условия сравнения.
Хотелось бы сделать по-правильному. Как это сделать на этом игрушечном примере?

P.S. Логика подсказывает, что нужно определить границы, задать начальные условия и стартовать этот механизм.
...
Рейтинг: 0 / 0
01.06.2012, 09:02
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37820861
F#
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
F#
Гость
Если порядок исполнения выражения в C# определен, то можно так
Код: c#
1.
2.
3.
        public bool IsChildOf(ColumnViewTreeItem item) {
            return Parent != null &&  (Parent == item || this == item || Parent.IsChildOf(item));
        }



Правда тут теперь нет хвостовой рекурсии, но C# кажись и так ее не не обрабатывает
...
Рейтинг: 0 / 0
01.06.2012, 09:25
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37820869
F#
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
F#
Гость
Еще parent == item можно убрать
...
Рейтинг: 0 / 0
01.06.2012, 09:28
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37820879
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
лучше циклом
...
Рейтинг: 0 / 0
01.06.2012, 09:30
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37820882
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k0rvin
Участник
enigmaticИмеется простейшая структура данных: дерево, где элемент имеет ссылку на родителя.
Нужна функция, определяющая, является ли один элемент дочерним для второго.

Пишу функцию, которая бы просто делала то, что мне нужно:
Пишу рекурсивную функцию следующим образом (мой код на C# просто потому что мне так удобнее):
Код: c#
1.
2.
3.
4.
5.
public bool IsChildOf(ColumnViewTreeItem item) {
    if (Parent == null) return false;
    if (Parent == item || this == item) return true;
    return Parent.IsChildOf(item);
}


Я вижу, что она может быть реализована лучше: здесь присутствует разлапистый if, неудобно определены условия сравнения.
Хотелось бы сделать по-правильному. Как это сделать на этом игрушечном примере?

P.S. Логика подсказывает, что нужно определить границы, задать начальные условия и стартовать этот механизм.

Код: c#
1.
2.
3.
4.
5.
public bool IsChildOf(ColumnViewTreeItem item) {
    if (this == item) return true;
    if (Parent == null) return false;
    return Parent.IsChildOf(item);
}


или
Код: c#
1.
2.
3.
public bool IsChildOf(ColumnViewTreeItem item) {
    return (this == item) || ( Parent != null && Parent.IsChildOf(item) );
}
...
Рейтинг: 0 / 0
01.06.2012, 09:32
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37820888
F#
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
F#
Гость
Или без рекурсии (побережем стек) правда теряем возможность перекрыть IsChildOf для каких-то видом айтемов
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
public bool IsChildOf(ColumnViewTreeItem item) {
    var current = this;
    while (curent != null && curent != item)
    {
         current = curent.Parrent;
    }
    return curent == item;
}
...
Рейтинг: 0 / 0
01.06.2012, 09:33
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37820892
enigmatic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
enigmatic
Участник
F#,

Спасибо, так гораздо лучше.

Яростный Меч,

Нет. В данном случае - нет.

k0rvin,

Спасибо. Значит, все-таки я недалеко от истины ушел.
...
Рейтинг: 0 / 0
01.06.2012, 09:36
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37820911
enigmatic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
enigmatic
Участник
Признаться, все это очень интересно:
>Если порядок исполнения выражения в C# определен
>Правда тут теперь нет хвостовой рекурсии
>C# кажись и так ее не не обрабатывает
>без рекурсии (побережем стек) // то, что всегда можно без рекурсии

>правда теряем возможность перекрыть IsChildOf для каких-то видом айтемов
Почему?

>(побережем стек)
Дерево обещает быть небольшим, но спасибо за то, что обратили внимание.
...
Рейтинг: 0 / 0
01.06.2012, 09:46
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37821016
F#
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
F#
Гость
enigmatic>правда теряем возможность перекрыть IsChildOf для каких-то видом айтемов
Почему?


Потому, что потомок не вызывает isChildOf родителя. Если вдруг у родителя какая-то своя реализация (например нескольо парентов) то она не отработает.
...
Рейтинг: 0 / 0
01.06.2012, 10:44
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37821367
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
enigmatic public bool IsChildOf(ColumnViewTreeItem item) {
if (Parent == null) return false;
if (Parent == item || this == item) return true;
return Parent.IsChildOf(item);
}

Иногда практика сама подсказывает в каком порядке и как проверять. Бывают случаи
когда например одна проверка срабатывает в 0.001% случаев а другие в 99.999%.
Тогда эти проверки в коде просто меняют местами. Казалось-бы пустяк но на рекурсии
или каких-то особо жостких численных методах это важно.

Если терпит я вечером полистаю книгу. Кажется "Жемчужины программирования" там
были примеры профиляторов для таких предикатов.
...
Рейтинг: 0 / 0
01.06.2012, 12:57
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37822065
Lelouch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lelouch
Участник
mayton,

если в данном случае поменять проверки местами, то есть шанс схватить исключение.
...
Рейтинг: 0 / 0
01.06.2012, 20:10
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37822073
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Какое исключение?
...
Рейтинг: 0 / 0
01.06.2012, 20:18
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37822105
Фотография eNose
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
eNose
Участник
[не активирован]
[не одобрен]
Яростный Мечлучше циклом +1

простой перебор по парентам до искомого родителя / корня.
и никаких рекурсий там ненадо в принципе.
...
Рейтинг: 0 / 0
01.06.2012, 20:43
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37822159
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Вам тут видимо больше делать нечего, как обсуждать три несчастные строчки кода?
...
Рейтинг: 0 / 0
01.06.2012, 21:33
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37823653
enigmatic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
enigmatic
Участник
Яростный Мечлучше цикломeNose+1

простой перебор по парентам до искомого родителя / корня.
и никаких рекурсий там ненадо в принципе.Всегда лучше или только в данном случае?
...
Рейтинг: 0 / 0
04.06.2012, 07:41
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37823656
enigmatic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
enigmatic
Участник
mayton,
Терпит, но спасибо.

MasterZiv,
Вам тут видимо больше делать нечего, как обсуждать как другие обсуждают три несчастные строчки кода?
...
Рейтинг: 0 / 0
04.06.2012, 07:45
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37823671
Фотография eNose
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
eNose
Участник
[не активирован]
[не одобрен]
enigmaticВсегда лучше или только в данном случае? рекурсия нужна ровно для наоборот - обойти дерево (часть дерева), начиная с какого-то элемента. рекурсивно вызывая саму себя, есть возможность вернуться на предыдущий элемент.

зачем при проверке на парент использовать рекурсию, если у дочернего всегда ОДИН родитель?

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


по ресурсам - второй способ менее прожорлив.
по скорости - зависит от количества элементов и количества уровней вложения. тут не угадаешь :)
...
Рейтинг: 0 / 0
04.06.2012, 08:33
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37825147
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
Яростный Мечлучше циклом+1
...
Рейтинг: 0 / 0
05.06.2012, 01:27
| Ответить | Цитировать | Написать  
Рекурсия. Как правильно?
    #37825150
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
enigmaticЯростный Мечлучше цикломeNose+1

простой перебор по парентам до искомого родителя / корня.
и никаких рекурсий там ненадо в принципе.Всегда лучше или только в данном случае?
всегда, когда потребление памяти - константа.
...
Рейтинг: 0 / 0
05.06.2012, 01:29
| Ответить | Цитировать | Написать  
19 сообщений из 19, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Рекурсия. Как правильно?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=37822105&tid=1342237]:
 0ms
get settings:
 9ms
get forum list:
 15ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 142ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 57ms
get tp. blocked users:
 1ms
others: 237ms
total:  476ms
созд. / загр.: 476ms
x
x
Закрыть


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