Рекрусия

Гелдам доста често има въпроси за рекурсия...

Използването на рекурсия не е ли дизайн-смел вече? Говоря за хай-левел програмиране за бизнес приложения. Дори и на рекурсивни структури може да се направи добро АПИ, за да не се налага рекурсия, която е доста трудна за начинаещи девелопери.

--
Sometimes the sole purpose of your life is to serve as a warning to others.

mhm? koj e kazal, che wsichko e za wseki? za nqkoj rekursiwni algoritmi nerekursiwnite warianti sa mnogo, mnogo, mnogo po-kofti tyj che edwa li shte ulesnqt mnogo debiloperite, wij za developerite nqma proble bili te nachinaeshti ili ne ;)

Ами аз друго имам впредвид - гледам, че в .НЕТ АПИ-то яко бягат от това на девелоперите да им се налага да ползват рекурсия - примерно System.WinForms.TreeView - treeview-то по принцип е рекурсивна структура, но примерно в парент клас-а е изнесена колекция (ArrayList) от висчки Nodes, така че можеш да си ги обходиш с foreach и лесно да стигнеш до parent / child nodes с пропертита. Също и има методи:

FindNodeByValue()
FindFromKey()

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

--
Sometimes the sole purpose of your life is to serve as a warning to others.

по принцип одобрявам идеите на .NET, в часност - улесяването на програмиста с помощта на добре струтурирани и лесни за използване алгоритми, структури от дани и etc. първо примера ти ми се стори пълен дебилизъм, но като се замисля;

do_something(node) {
// do it
if (left) do_something(node.left);
if (right) do_something(node.right);
}
do_something(root);

foreach (nodes as node) {
// do it
}

...не изглежда зле :)

В .NET съзнателно се избягва рекурсията за да станат нещата по-прости за начинаещите програмисти. Разбира се всеки има право да си я използува колкото иска. Аз лично смятам че тя е от основните принципи на програмирането въобще.

Някой беше казал, че в .NET "линеаризацията" на рекурсивните структури се извършва с помощтта на паралелна нишка, която обхожда рекурсивно структурите и блокира, докато текущо посетения възел не бъде прочетен през "линейното" API, след което навесятва съседен възел и пак блокира и т.н. докато не бъде обходена цялата рекурсивна структура. Не знам дали действително е така, но изглежда смислено (или най-малкото мързеливо).

"Всички науки са или физика, или колекциониране на пощенски марки." (Е. Ръдърфорд)

e stiga
rekursiqta beshe edno ot pyrvite neshta deto sym razbral v tova programirane kogato sym pro4el kvo e tova algoritym i struktura ot danni
v na4aloto programirah na Turbo Byzik (Basic:)) i tova rekursiq beshe mnogo ne ponqtno,
no sled tova kato se sbluskah s Pascal-a, tova si mi dojde neshto estestweno (rekursiqta de)
ne moga da razbera koe i e trudno-to
4ovek kojto malko mu vyrvi matematikata i razbira kvo e rekurentna vryzka, nqma na4in da ne go razberat

abe ne znam,
znam 4e ima takiva hora koito naistina shte im e trudno da se sprawqt s tova, no si mislq za kakvo wyobshte sa zapo4nali s tova

otkazwajte se hora, ne e tova priznanieto vi, bydete sigurni:)

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

Спестява написването на допълнителна функция (която да се извиква рекурсивно) и се заменя това само с един цикъл. Кодът се чете по-лесно, вместо да се налага да се търси тази рекурсивна функция, да и се предават параметри и цялата хамалогия. Разбира се това премахва нуждата от рекурсия в 90% от случаите, но в останалите 10 си трябва.

Life has lots of twists and turns. Don't get too comfortable.

Ами как да ти кажа, да вземем за пример едно двоично балансирано дърво, в което има 2^32 елемента ( например ), с една рекурсия, за да намериш елемент, ще направиш най-много 32 рекурсивни извиквания. Ти линейно ли предпочиташ да ти се подават/обработват данните?

Хайдеее рекурсията в казана, утре if-овете, а по-нататък и циклите може да махнат в .НЕТ
Шегувам се

>> с една рекурсия, за да намериш елемент, ще направиш най-много 32 >>рекурсивни извиквания.

Ами не... нали е .НЕТ... всъщност ще направя едно нерекурсивно извикване на FindNodeByValue( ... ) - а там вече професорите от MIT дето бачкат в Майкрософт ще му мислят за 32-те рекурсивни извиквания. :)

Аз просто искам да покажа на екрана един текст в червено, да си взема заплатата и да ходя да пия :) Сега друг в въпроса, че няма да знам, че в едни структури се търси за O(log n), а в други не и навярно направо ще си ползвам само ArrayList - ама какво от това, нали има не повече от 500 nodes и машината е PIV 3 Ghz - така че, все тая.

--
Sometimes the sole purpose of your life is to serve as a warning to others.

Ми да - както Перин каза в 90% от случаите е доста удобно да ползваш линеен код за рекурсивни структури - примерно искаш да увеличиш с 1 стоийността на всички елементи в двоично дърво:

...
foreach (MyNodeType node in BinaryTree.Nodes)
{
node.Value = node.Value + 1;
}
...

Иначе решението с рекурсията е по грозно и неясно за по-малко опитни членове на екипа.

--
Sometimes the sole purpose of your life is to serve as a warning to others.

"Иначе решението с рекурсията е по грозно и неясно за по-малко опитни членове на екипа"

za "grozno"-to nishto ne kazavam, vkusut za neshtata e razlicen za vseki chovek, za men primerno e po-krasivo rekursivno da si obhojdash durvoto, a ne da izpolzvash nqkakvi "lineini" strukturi, koito vsushtnost pak sa rekursivni. za "neqsno"-to obache ne sum suglasen... mi da se spasqvat we "po-neopitnite", kato sa otishli da rabotqt tazi profesiq bez da mogat edno tupo durvo da obhodqt za kvo si govorim... ai siktir ot nedocheli, tuk ne stava vupros za neshto zasukano ami za neshto tolkova fundamentalno, che bez nego ne bi trqbvalo da naemat na rabota, ama tva si e samo moe mnenie...

Има 2 типа програмисти - едните гледат да си свършат работата достатъчно добре, максимално бързо и с минимални усилия. За да ходят послят да пият, както казва Гуру (съответно да спят, ебат, ядат, гледат мач, багат из парка или квото там ги кефи). И с това постигат максимален ефект както за себе си, така и за фирмата, в която работят.
Другите живеят пред монитора, пишат яки цикли и двойно свързани списъци и носят тениски с пингвини или чаши кафе. Познай при тях какъв е ефекта от работата им, колко добре се свършва, колко бързо и с колко усилия.

priatelite.net - Твоите приятели!

Не става дума дали трябва да го пишеш дървото или да не го пишеш, ама самия факт, че нивото на програмистите е паднало до там, че обхождане на дърво да се смята за 'advanced', въобще не говори добре.

Сигнатура!

Ми какво да ти кажа, въпрос на гледна точка. Според мене изискванията са се променили. Отвреме навреме ми се налага да работя с други по нещо, което ръководя, и съм забелязал, че великите програмисти не са ми от голяма полза. Работата вършат хора, които разбират какво трябва да се направи и как, дори и да се затрудняват от някои по-сложни неща.

priatelite.net - Твоите приятели!

Не знам защо тоя 'термин' 'велики програмисти' се използва и за надути тъпи копелета и за опитни програмисти едновременно?

Колкото до изискванията - еми да ако пишеш ASPXYZ и редиш форми - наистина няма особена нужда от 'доброто старо програмиране'.

Сигнатура!

>> че обхождане на дърво да се смята за 'advanced'

Ами да... предполагам повече от половината работа в света свързана с програмиране е малко или повече свързана с репортинг - вземи тези данни и ми ги покажи в такъв грид / чарт. Не виждам защо да е необходимо да си Нобелов лауреат, за да се справиш с това...

Така че обхождане на дърво си е наистина 'advanced' ако питаш мене и на повечето хора дори не им се налага да знаят какво е дърво, камо ли да го обхождат. Ама това не би им пречило да си вършат добре работата, която не е свързана с дърва.

--
Sometimes the sole purpose of your life is to serve as a warning to others.

предполагам повече от половината работа в света свързана с програмиране е малко или повече свързана с репортинг - вземи тези данни и ми ги покажи в такъв грид / чарт.

Крайно време е да се измисли име на нова професия или за тази половина от свете или за другата... Най-малкото не искам да имам еднаква професия с лелката от Първа инвестиционна, дето е много куул и реди репорта с 15 секунди по-бързо от съседната кака, която пък има 7 сертификата и обяснява на лелката колко са и неефективни рипортите.

Сигнатура!