В C# хорошо ли использовать рекурсивные функции в алгоритмах?

Question

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

Но хорошо ли использовать рекурсию в C# при создании алгоритма? Правильно ли говорить в отношении C#, что рекурсивные алгоритмы приведут к тому, что ваш стек будет расти довольно резко (если количество вызовов очень велико), и это не будет вообще быстрым и может привести к переполнению стека. Или есть какая-то оптимизация, чтобы сделать рекурсивные функции эффективными?

Я был бы признателен, если бы вы дали некоторое сравнение (скорость, память, читаемость) между алгоритмами, использующими рекурсию в функциональных языках и C#.

Answer 1

Не использовать рекурсию в любом случае заставит вас переписать свой алгоритм, используя свой собственный «стек», который в конечном итоге будет подвергнут аналогичным условиям во время выполнения.

Вы можете настроить размер стека в зависимости от потребности в вашем алгоритме, но если вы посмотрите на алгоритмы WPF/Silverlight и обычного UI, все они рекурсивны по своей природе, и каждый клик, каждое нажатие клавиши и каждое уведомление проходят через множество рекурсивных методов.

Заканчивать Creating Thread with Custom Stack Size,

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

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

Answer 2

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

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

Answer 3

Этот пост Recursive iterator performance подробно объясняет разницу между рекурсивной версией и нерекурсивной операцией. Результаты интересны. Отъезд

Answer 4

В текущей реализации Microsoft компилятора C# оптимизация хвостовых вызовов не производится. Это делает функциональные алгоритмы, которые рекурсивно переполняют стек. Хотя я бы не рекомендовал использовать глубоко рекурсивные алгоритмы в C#, методы, которые не требуют глубокого анализа, не должны вызывать никаких проблем.

Answer 5

Когда вам нужна рекурсия, вам это нужно, например, для обработки дерева по глубине или рекурсивного спуска.

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

Answer 6

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

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