Какво представлява рекурсията и защо е толкова важна за писането на ефективен компютърен код?
Рекурсията е един от най-разпространените методи в модерното програмиране. Тя помага за писането на по-прилежен код и е ключова в много модерни програми, но какво точно е рекурсия и защо всеки трябва да се запознае с този метод?
Дори да не сте програмист, рекурсията ще ви помогне да погледнете на много проблеми от друг ъгъл. Например, нека си представим, че седите на опашка и чакате да изтеглите пари от банкомат.
Тъй като опашката е твърде голяма, ще ви отнеме много време да преброите всички които трябва да изчакате за да изтеглите. Освен това трябва да изминете някакво разстояние, за да стигнете до първия, който в момента тегли. През това време някой може да вземе мястото ви. Няма ли по-лесен начин?
Има! Точно той използва рекурсия.
Попитайте човека пред вас колко хора остават да теглят пари пред него. Тъй като може би и той не знае. Най-вероятно той ще попита човека пред него и така докато не се стигне до този, който тегли в момента. Когато това се случи, човекът който тегли ще каже на този след него, че отговорът е нула, тъй като в момента тегли пари и пред него няма никой.
Точно това е рекурсия. След като се сдобие с тази информация, предпоследният ще добави едно, тъй като той трябва да изчака теглещия в момента и ще върне отговора си на този след него, че му остава един човек.
Този след него ще добави едно, тъй като трябва да изчака този пред него и теглещия и така ще върне своят отговор на човека, който е след него на опашката. Това ще се повтори, докато не се стигне до вас.
В този момент вие вече ще знаете точно колко човека трябва да изчакате, без да сте се мръднали от мястото си и запазили своя ред.
В програмирането рекурсивна е всяка функция, която вика себе си по време на самото изпълнение на кода. В примера с банкомата псевдокодът ще изглежда така:
Ако няма никой пред вас, върнете отговор 0, в противен случай върнете отговора на човек пред вас +1.
Както може да се види, за всеки човек тази функция ще върне различен отговор, спрямо позицията му на опашката.
Рекурсията има много други приложения, главно за решаването на сложни проблеми, за които не е намерено точно решение. Но какви са минусите?
Рекурсията заема много памет. Например, ако искате да намерите 100,000,000-ното число от редицата на Фибоначи, можете да го направите рекурсивно.
Започвате от 0,1 и след това събирате двата члена за да намерите третия. Събирате втория и третия, за да намерите четвъртия, но както виждате това ще отнеме доста време и ще е невъзможно без компютър.
В този случай рекурсията не е особено удобна, тъй като имаме математически изведена точна формула, която ни дава резултата. Или по-точно формулата на Бине.
В нея Fn е n-тият член на редицата на Фибоначи а фи е златното сечение – приблизително 1,6. Другата гръцка буква – пси е просто отрицателната стойност на златното сечение.
Това изчисление е много по-бързо за компютрите, отколкото събирането на милиони членове от редицата с рекурсия.
Сега, накрая, ще ви дам една логическа задача, свързана с рекурсията. Може да ми пратите отговорите на gvburnaski@gmail.com.
Вие и 10 ваши приятели сте отвлечени от извънземни. Те обаче не искат да ви изядат веднага и затова ви нареждат в редица по височина, като най-високият е отзад, а най-ниският отпред. След това поставят шапка на главите ви в произволен цвят – или черен, или бял.
Най-високият от вас вижда всички шапки, без своята, а най-ниският нито една. Извънземните ви казват че всеки от вас трябва да познае цвета на шапката си, като се започне от най-високия, в противен случай ще ви изядат всичките, но тъй като играта е трудна ви дават шанс за една грешка. Каква е стратегията за победа в тази игра?
За подсказка: включва рекурсия.
Очаквам отговорите ви…
