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

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

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

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

Ответы

Ответ 1

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

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

Отметьте Создание потока с пользовательским размером стека,

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

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

Ответ 2

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

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

Ответ 3

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

Ответ 5

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

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

Ответ 6

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

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