Итеративни и рекурсивни процеси

Рекурсивна функция за пресмятане на факториел

(define (fact n)
	(if (= n 0) 1 (* n (fact (- n 1)))))

Примерна оценка на (fact 4):

Основни характеристики на рекурсивния процес:

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

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

Итеративна функция за пресмятане на факториел

(define (fact n)
	(define (iter k res)
		(if (> k n) res (iter (+ k 1) (* res k))))
	(iter 1 1)
)

Примерна оценка на (fact 4):

Основни характеристики на итеративния процес:

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

Итеративният процес се изпълнява по-ефективно на Фон-Нойманови машини, понеже има директни хардуерни еквивалентни на понятията променлива (клетка от паметта), стъпка (такт на процесора), присвояване на стойност (прехвърляне на стойност на клетка от паметта). Рекурсивна функция, която моделира итеративен процес се нарича акумулаторна, понеже натрупва резултата в аргументите си. Тъй като при такава рекурсия не е важен процесът на свиване, не е задължително да се пазят всички състояния от развиването на рекурсията, той се полага на оптимизации. Това е имплементирано в съвременните реализации на Scheme. 

Защо различаваме итеративни и рекурсивни процеси

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

Итерация или рекурсия - това е въпросът

За разлика от Хамлетовия вечен въпрос, възможностите тук не са взаимно изключващи се. Повечето задачи се решават еднакво "леко" с итеративен и рекурсивен процес. Има обаче задачи, при които един от подходите е по-подходящ. Въпрос на тренинг и програмистка интуиция е да разпознаваме кога един от подходите е по-добър. Една особеност на рекурсивния процес е, че изчислението (при свиването на рекурсията) става в ред обратен на реда на дефинирането му (при развиването). Затова рекурсията е по-подходяща за решаване на задачи, в които е заложено такова обръщане - например превръщане на число от десетична в двоична бройна система. При "прави" задачи - такива при които процесът на решение и изчислението вървят в една посока, пък е по-подходящ итеративния процес - например намиране на корен на функция по метод на разполовяването. При задачи, при които този ред няма значение и тогава и двата метода са еднакво ефективни. Итерацията често се предпочита заради ефективността й. Рекурсията се предпочита, когато се търси простота на изразяване. Счита се, че рекурсивни програми в общия случай се доказват по-лесно, понеже при тях директно може да се приложи метода на математическата индукция. Итеративните програми пък често се базират на математическо свойство, за което се доказва, че е валидно по време на целия итеративен процес и при сходимост (завършване) на процеса води до решение на задачата. Основното предимство на рекурсията пред итерация е възможността за разклоняване на рекурсивния процес. В такива случаи много прости рекурсивни зависимости водят до сложни процеси, които по-трудно се моделират с итерация.

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