Ползите от рекурсията
В този пост ще разгледам рекурсията, използвайки класически пример - изчисляване на факториал. В по-сложни ситуации ефектът от използването на рекурсия (както положителна, така и отрицателна) може да бъде много по-голям.
Компактност на записа
Така че нека сравним нотацията на функции, които изчисляват факториал, използвайки рекурсия и без да използват рекурсия. Оказва се, че слуховете за тромавостта на рекурсията са до голяма степен преувеличени.
Бърза странична бележка: за краткост всичките ми реализации (както рекурсивни, така и нерекурсивни) ще бъдат доста прости. Например няма да проверявам верността на въведените данни (отрицателно число, изобщо не число). Ще засегна надеждността на кода по-долу.
Мнозина биха могли да кажат, че функцията е прекалено сложна от добавянето на променливата i. По-долу ще обясня защо направих това, но засега ще дам класическа версия:
Този подход има един основен недостатък и скоро ще се върнем към него. Засега нека разгледаме рекурсивните реализации.
Първо, класическо изпълнение с рекурсия, всичко в един и същ Python:
Обърнете внимание колко точно тази нотация отразява математическата дефиниция на факториал.
Можете да запазите един ред:
Същата мисъл може да бъде записана още по-компактно.
Този пример работи само в Python 2.5 и по-стари.
Ето два примера в Haskell:
Ще цитирам още един, по-компактен, но съвсем разбираем за неподготвен читател:
Могат да бъдат дадени много повече изпълнения на факториално изчисление, но ми се струва, че дадените примери са достатъчни, за да разсеят мита, че рекурсивните внедрения са тромави.
Според мен ситуацията е обратна: в случаите, когато рекурсията е оправдана, това може значително да намали количеството код и да го направи много по-ясен.
Как можете да подобрите разбираемостта на кода, използвайки рекурсия?
Неизменност на променливи
При програмирането може да бъде полезно да се придържате към концепцията за неизменност на променливите (много езици за програмиране изобщо не позволяват променливи промени). Това ви позволява да убиете много птици с един камък:
- Първо се отървавате от странични ефекти - странични ефекти, свързани с факта, че една и съща променлива приема различни стойности по различно време;
- второ, можете лесно да проверите данните за коректност; достатъчно е да го направите веднъж и всички проверки могат да бъдат групирани, да речем, в началото на функция; това увеличава не само надеждността на кода, но и неговата четливост, а също така ви позволява да не забравяте нищо;
- трето, значително увеличавате четливостта на кода, тъй като читателят няма нужда да преглежда целия код, за да проследи развитието на променлива; достатъчно е да намери мястото, където стойността е присвоена на променливата, и тогава той може да бъде сигурен, че тази стойност няма да се промени.
Нека разгледаме по-отблизо тези аспекти.
Отърви се от страничните ефекти
Помислете за рекурсивно и нерекурсивно изпълнение. Ще ги повторя тук.
Не рекурсивно (един от тях, по-добре ми харесва; защо - ще обясня по-долу)
Тук виждаме две променливи променливи едновременно - f и i. Освен това i влияе f на едно място и променя стойността му на друго. Това е потенциален източник на грешки от този вид:
Дори в такъв тривиален код не е лесно да се открие грешката. С увеличаването на количеството код става много трудно да се открият грешки, свързани със странични ефекти.
Опцията за рекурсия е напълно свободна от този недостатък (ще го дам отново тук):
По време на изпълнението на функцията fac не се променя променлива. Това обстоятелство може значително да опрости четенето и разбирането на кода.
Променливата неизменност предоставя още едно ценно предимство: всяка променлива има точно определена цел, която не може да бъде променена.
Лекота на валидиране на стойности
Тъй като стойностите не се променят, те могат лесно да бъдат проверени за коректност. Освен това всички проверки могат да бъдат групирани, без да се страхуват, че променливата ще се промени до момента, в който се извършат някои действия върху нея.
Строго погледнато, проверката се превръща в напълно естествен клон на съществуващия алгоритъм. Ето модифициран пример 3:
За да приложите подобна проверка в нерекурсивна версия на кода (примери 1 и 2), ще трябва да добавите отделен механизъм за проверка. И това не е случайно, причините се крият в различен подход при работа с данни. Ще се върна към тези разлики в раздела „Програми, управлявани от данни спрямо програми, управлявани от данни“ „.
Еднозначно присвояване на всяка променлива
Всъщност, ако променливите запазват своите стойности, тяхното предназначение остава строго непроменено. В комбинация с подходящи имена това обстоятелство може да бъде безценно при четене и отстраняване на грешки в кода.
Погледнете още веднъж рекурсивен пример 3: променлива n запазва едно задание.
За да направим идеята по-ясна, нека въведем още една променлива (разбира се, тя също ще бъде неизменяема):
Сега има две променливи и тяхното значение е еднакво, където и да се използват: n е аргумент, f е факториал на n (и нищо друго).