зачем тогда рекурсия??)
Иногда циклом прям пипец сложно
Tishka17
Andrey
Kirill
У рекурсии минус - повышенное потребление памяти. И если заранее не известна максимальная глубина рекурии, то лучше её не использовать.
Alex
Ребят, в каких ситуациях рекурсия заменяет простой цикл?
во-первых не всякую рекурсию можно выразить простым циклом.
Kirill
во-первых не всякую рекурсию можно выразить простым циклом.
Человек наоборот хочет цикл заменить на рекурсию
koder
во-первых не всякую рекурсию можно выразить простым циклом.
Если не ветвится то всегда можно имитировать стек списком ))))
Anonymous
тогда это цикл будет
Tishka17
class Node:
value: int
children: List[Node]
Дмитрий
Дерева
чтоб ходить околоциклом по дереву которое хранится не в массиве (бинарные так хранят вроде иногда), а как ты описал - BFS
Alex
во-вторых т.к. глубина рекурсии в питоне ограничена и нет оптимизации хвостовой рекурсии - рекурсию стоит применять только если известно что глубина не превысит лимит.
Anonymous
во-вторых т.к. глубина рекурсии в питоне ограничена и нет оптимизации хвостовой рекурсии - рекурсию стоит применять только если известно что глубина не превысит лимит.
если не ошибаюсь 995 глубина рекурсии в питоне
Valery
Anonymous
def f(): f()
Anonymous
и вызови
Anonymous
Alex
верней конкретное значение зависит
Anonymous
Значит от компа зависит
Ｆｏｒｅｖｋａ ÐΞV
на самом деле зависит от системы
Anonymous
чтоле
Anonymous
да
Дмитрий
и вызови
тот же dfs проще сделать рекурсией вроде. разные сортировки которые за n*logn работают
Anonymous
Прикольно, а это от оперативы зависит глубина рекурсии
Дмитрий
ну то есть написать merge рекурсивно я смогу быстро, над циклическим вариантов придется подумать
Ｆｏｒｅｖｋａ ÐΞV
Bfs без рекурсии в студию
вот https://github.com/Forevka69/Graphs/blob/master/Graph/Graph.py#L93
Ｆｏｒｅｖｋａ ÐΞV
курсовая по матеше
Aragaer
если есть tail call optimization, а рекурсия хвостовая, то она ничем не отличается от цикла
Alex
ты можешь ее настроить, но лучше этого не делать
Alex
ну и да зависит от размера стека
Tishka17
вот https://github.com/Forevka69/Graphs/blob/master/Graph/Graph.py#L93
Да, он прям такой же просто как рекурсивный!
Anonymous
нет, максимальная глубина рекурсии по-умолчанию зашита в интерпретатор
но экземпляры функций занимают место в памяти какое-то
Anonymous
пока процесс длится
Anonymous
значит и от оперативы в какой то мере
A.
какая кафедра?
какие альтернативы?
ФДО Тусур информатика и вычислительная техника. Есть ещё направления "программное обеспечение средств вычислительной техники и автоматизированных систем" , и "системы автоматизированного проектирования", ну и прикладная информатика в экономике (не привлекает)
Anonymous
ну да ладно
Alex
такие наивные рассуждения как-то даже не хочется комментировать
Дмитрий
А если надо просто сумму?
чтоб посчитать сумму - надо пройтись по всем вершинам. это можно сделать или рекурсивным dfs или нерекурсивным bfs.
Valery
ФДО Тусур информатика и вычислительная техника. Есть ещё направления "программное обеспечение средств вычислительной техники и автоматизированных систем" , и "системы автоматизированного проектирования", ну и прикладная информатика в экономике (не привлекает)
ФДО это же дополнительного
не на дневной?
Tishka17
чтоб посчитать сумму - надо пройтись по всем вершинам. это можно сделать или рекурсивным dfs или нерекурсивным bfs.
Да я в курсе. Речь шла о том, что иногда рекурсивный алгоритм сильно проще
Aragaer
по-моему в SICP есть фраза, что "цикл это просто синтаксический сахар над хвостовой рекурсией"
Дмитрий
Да я в курсе. Речь шла о том, что иногда рекурсивный алгоритм сильно проще
ну кому как, мне bfs проще кажется.
Ｆｏｒｅｖｋａ ÐΞV
но благодаря генераторам можно всё переписать без рекурсии
Valery
Факультет дистанционного обучения
а смысл на заочку?
цель какая? корочки получить или научиться?
Ｆｏｒｅｖｋａ ÐΞV
да собственно и без них тоже можно, но да, будет сложнее чем с рекурсией
Aragaer
если есть очереди (любые fifo), то можно любую рекурсию свести к итерации по этой очереди