Есть ли что-нибудь, что может быть достигнуто только рекурсией?

Question

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

Answer 1

Вы всегда можете симулировать рекурсию, сохраняя свой собственный стек. Так что нет.

Answer 2

Вы должны уточнить, о какой рекурсии вы говорите. Есть алгоритмическая рекурсия и есть рекурсия в реализации . Это правда, что любой рекурсивный алгоритм допускает прямую нерекурсивную реализацию - это легко сделать, используя стандартный прием моделирования рекурсии с ручным стеком.

Однако в вашем вопросе упоминаются алгоритмы * только 1012 *. Если предположить, что речь идет именно об алгоритмической рекурсии, то ответ будет да , существуют алгоритмы, которые по своей природе и неизбежно являются рекурсивными. В общем случае невозможно заменить изначально рекурсивный алгоритм нерекурсивным. Самый простой способ построить изначально рекурсивный алгоритм - это сначала взять изначально рекурсивную структуру данных . Например, скажем, нам нужно пройти по дереву только с родительскими связями (без дочерних с родителями). Невозможно придумать разумный нерекурсивный алгоритм для решения этой проблемы.

Итак, это один пример для вас: обход дерева, который имеет только родительские ссылки, не может быть выполнен нерекурсивным алгоритмом.

Другим примером изначально рекурсивного алгоритма является известный алгоритм QuickSort. Быстрая сортировка всегда рекурсивна и не может быть превращена в нерекурсивный алгоритм просто потому, что если вам это удастся, она больше не будет быстрой сортировкой. Это будет совершенно другой алгоритм. Конечно, это звучит как упражнение в чистой семантике, но, тем не менее, это то, что стоит упомянуть.

Answer 3

Ниже сравниваются рекурсивные и нерекурсивные реализации: http://www.sparknotes.com/cs/recursion/whatisrecursion/section1.html

Выдержка:

Учитывая, что рекурсия в целом менее эффективна, зачем нам ее использовать? Существует две ситуации, когда рекурсия является лучшим решением:

1. Проблема гораздо яснее решается с помощью рекурсии: существует много проблем, когда рекурсивное решение является более ясным, чистым и гораздо более понятным. Пока эффективность не является первостепенной задачей или если эффективность различных решений сопоставима, вам следует использовать рекурсивное решение.
2. Некоторые проблемы гораздо проще решить с помощью рекурсии: есть проблемы, которые не имеют простого итеративного решения. Здесь вы должны использовать рекурсию. Проблема Ханойских Башен - пример проблемы, где итеративное решение было бы очень трудным. Мы рассмотрим Ханойские башни в следующем разделе этого руководства.

Answer 4

Если я правильно помню свои алгоритмы, нет ничего выполнимого с помощью рекурсии, которое нельзя сделать с помощью стека и цикла. Однако у меня нет формальных доказательств здесь.

Изменить: мне приходит в голову, что ответ, возможно, заключается в том, что единственное, что можно сделать с помощью рекурсии, что невозможно с помощью цикла стек +, это переполнение стека?

Answer 5

Вы просто ищете практический пример рекурсии? Недавно мы с друзьями внедрили функцию Haar Wavelet (в качестве упражнения для начала изучения Ruby), которая, казалось, требовала рекурсии. Разве у кого-нибудь есть реализация без рекурсии?

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