Рекурсия или итерация? - PullRequest
Новая
       56

Рекурсия или итерация?

29 голосов
/ 26 января 2009

Я люблю рекурсию. Я думаю, что это сильно упрощает вещи. Другой может не согласиться; Я думаю, что это также делает код намного проще для чтения. Тем не менее, я заметил, что рекурсия не так часто используется в таких языках, как C #, как в LISP (что, кстати, является моим любимым языком из-за рекурсии).

Кто-нибудь знает, есть ли веские причины не использовать рекурсию в таких языках, как C #? Это дороже, чем итерация?

Ответы [ 14 ]

1 голос
/ 26 января 2009

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

Если проблема требует рекурсии (например, древовидная навигация), тогда я повторяю.

При этом я делаю линейку бизнес-приложений на C # - я уверен, что к научному программированию предъявляются другие требования.

0 голосов
/ 27 января 2009

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

for(int i=0; i < 3; i++) doIt(i);

фактически сделаны с рекурсией. Нечто эквивалентное 

public rediculous(i) {
    doIt(i);
    if (i < 3) rediculous(i + 1);
}

Я бы на самом деле привел здесь пример XSLT, но все это печатание заставляет Младенца Иисуса плакать.

0 голосов
/ 26 января 2009

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

0 голосов
/ 26 января 2009

Я думаю, что рекурсивные функции должны быть помещены в стек - каждый раз, когда функция вызывает себя, другая копия этой функции помещается в стек функций и так далее. Проблема в том, что в какой-то момент стеку не хватает места для хранения функций, поэтому, если числа становятся большими, рекурсивное решение может не сработать. Я знаю, потому что это укусило меня в задницу - у меня была отличная рекурсивная функция для free() всего моего связанного списка, а затем я проверил его с самым большим связанным списком, который я мог сделать, и получил ошибку (я думаю, это было segfault - определенно должно было быть переполнение стека :)).

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

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

Страница:
...