Гейт споменавал съм и другаде, но като перловски човек, навсякъде ми се набиваше в главата — цикли, цикли, цикли. Ракурсивните са зло! Те са бавни! Не ги ползвайте! Всяка функция викаща сама себе си може да бъде заменена с цикъл, дори да не е очевидно всеки път. Ако сте особено извратени можете дори if да замените с for. Цикъла „за“ е велик, осланяйте се на него. И така нататък.
И така до миналата година, когато изведнъж Кънев направи доклад за сметосъбирачите на ОФ'13. И какво се оказа в един момент? Боклучиите имат особен проблем с циклите. И колкото и гениални решения да измислят, колкото и ракетна наука (буквално) да се влага в тях, проблема си остава. Течове на памет, грешки, много несгоди произлизат. И май се оказва, че на практика ракурсивните функции не са чак такова зло, нищо че няма да решаваме никога в реалността редичка на Фибоначи. Програмата може наистина да стане малко по-бавна, но пък много по-стабилна.
Сега на първо време ще направя уточнението че говоря от гледна точка на C - не за друго, а защото при C (апропо и при всеки не-JIT, не-интерпретаторен език) е най-лесно да разбереш какво всъщност става - дизасемблираш полученото binary и с малко общи познания за архитектурата и справки с документация по въпроса, имаш някаква относително добра идея какво става.
Рекурсивни срещу итеративни решения е нещо много дъвкано, безсмислено е да се повтаря, но все пак в общият случай рекурсивното решение е с порядъци по-бавно. Причината че колкото по-"навътре" влизаш, толкова повече алгоритъма става от cpu-bound към memory-bound, защото трябва да пазиш стек фреймовете някъде, за да може като привърши функцията да въстановиш регистрите както са си били преди да я изпълниш, да си вземеш изхода от функцията и т.н. Това дори да не е толкова "дебело", демек да не се наложи да се похабят повече от няколко десетки килобайта за целта, пак е много по-бавно. Итеративното решение на псевдоасемблер се свежда до нещо от сорта на това:
loop: cmp reg1, max
je end
...
inc reg1
end: ...
Рекурсивното се свежда до нещо от сорта на това:
...
cmp reg1,smth
jne next
ret
next:
...
push reg1
push reg2
...
call function
pop reg1
pop reg2
...
Разликата е че във вторият случай имаш много повече четене и писане в паметта (за да пазиш в стека състоянието на регистрите, return адреса, ако се налага стойността която връща функцията и тем подобни глупости). В първият случай оперираш върху регистри. Хората масово не си дават сметка колко бавен е достъпът до паметта. Ако имаш късмет и това нещо ти е в L1/L2 кеша, ще е десетки до стотици пъти по-бавно от достъпването на регистър. Ако нямаш късмет и не е кеширано - ами честито, стотици до хиляди до милиони ако е swap-нато на диска. Това всичкото също така изключва момента че големината на стека не е безкрайна и ако "слизаш" много "навътре" рано или късно ще те бият през ръцете.
Отделно в над 90% от случаите, рекурсивните алгоритми имат итеративна алтернатива, понякога да - доста трудно е да я измислиш и реализираш (обхождането на графи и дървета е горе-долу момента в който вдигам ръце, така или иначе там в много случаи итеративните решения там всъщност са рекурсивни само че ти сам менажираш собствен стек вместо това да става наготово хардуерно-подпомогнато, което в крайна сметка не е много по-умно, освен ако не ти е проблем голямата дълбочина на рекурсията).
Тааа за тоя java проблем не знам за какво иде реч, така че не мога да го коментирам.
Побитовото смятане е доста по-бърз метод например за запазване на състояние (в хиляди пъти), от колкото да речем локална променлива. Стига езика да ни го позволява де, защото май не съм го виждал в нещо по-модерно от C++.
Запазване на състояние?
Побитовите операции вършат едно и също в който и да било език. Определено не мисля че това се свежда само до C/C++, аз поне не знам за език, в който да няма побитови операции.
