Алтернатива на рекурсията


2
Здравейте колеги :)
Искам да попитам дали има някаква алтернатива на рекурсията? Имам предвид сортиращите алгоритми в лекцията за масиви - merge sort, quick sort...



Отговори



5
Всяка рекурсия може да се сведе до итерация. Теорема от СЕП-а (Семантика на езиците за програмиране).

от yonchoy (2134 точки)


0
Не си спомням лекциата за масиви, но мога да ти кажа, че между рекурсия и сортиращи алгоритми, няма нищо общо.
Дефинирай си въпроса по- точно.

от wooden_jesus (2128 точки)


0
да, ясно че нямат нищо общо :) просто решавам задачите от домашното за масиви и трябва да се напишат няколко сортиращи алгоритми, за които не намерих решение без рекурсия и ми е интерсно дали има такова.

от epitsin (1253 точки)

0
Има итеративни решения за merge sort и quick sort, дори в google ги има, но поне за мен са доста по-сложни от тези с рекурсия. http://www.softwareandfinance.com/CSharp/QuickSort_Iterative.html

от anilak (1134 точки)



2

Здравей, 

Нека поговорим малко за рекурсията.

Една функция е рекурсивна, ако извиква сама себе си.

Директно - void f() { f() } - или индиректно - void f() { g() }; void g() { f() };

По време на runtime-а на една програма се използва стек, в който, за всеки един активен метод (такъв който е стартирал и не е приключил), се запазва следната информация:

1. Локалните променливи

2. Параметрите на функцията

3.Адресът, от който трябва да продължи изпълнението на програмата, след като завърши.

Какво се случва при извикване на функция:

А. В стека push-ват 1, 2, 3.

Б. Точно преди return от функцията, адресът се запазва, информацията от стека се pop-ва.

В. Програмата продължава изпълнението си от запазения адрес.

Сега, след като имаме тази информация, отговорът е ясен: Безотказна алтернатива на всяка една рекурсия е използването на стек.

 


от simonkazakov (1116 точки)


0
Ако ще ползвам стек вместо рекурсия, що просто да не си увелича стека на програмата? Какво би станало, ако ми свърши хийпа... Или примерно въобще нямам хийп (можеш ли да се сетиш за пример кога това е вярно?). И какво става при опашата рекурсия, защо ми е да пазя локалните променливи? И опашата рекурсия трябва ли въобще да се пази нещо на стека? Виж какво излиза от компилатора като код. Виж какво е ABI, кои са използваните ABI-та. Виж какво е TCO.



2

Ето ти итеративен алгоритъм за Quick Sort -> http://pastebin.com/sDFvUk85 .Върви в същата сложност, като рекурсивния -n*log(n) за avarage case.В случая съм симулирал нещо като рекурсия на базата на стек.
Иначе всяка рекурсия на теория би трябвало да може да се сведе до итеративен алгоритъм.Ти си ползвай това, което ти е най-интуитивно, но недей да се плашиш от рекурсията, а просто я разбери.




2

Мога да препоръчам сайт, които демонстрира различни сортиращи алгоритми. Там може да тестваш и да видиш кое в каква ситуация е по-добре да се използва:

Sorting Algorithms


от Flyer (1848 точки)