алгоритми с рекурсия

Определение за алгоритъм: съвкупност от данни и правила за тяхната обработка, чието изпълнение в определената последователност води до очакван краен резултат.

Определението дава отговор на 3-те кардинални въпроса:

Кое - очакван краен резултат;

Как - в определената последователност;

Какво - съвкупност от данни и правила;

Произволна кулинарна рецепта е вид алгоритъм - също включва данни (продукти); правила и определена последователност за обработка; краен резултат.

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

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

1. Обработване на данни и изчисляване на резултат

Чрез изчислителен процес се обработва наличната информация с цел получаване на очакван резултат. При този вид дейност се ползват различни алгоритми, чийто основни свойства са: детерминираност (определеност), масовост (приложимост за всяка конкретна задача от дадения тип) и резултатност - след краен брой стъпки получаване на очакван резултат.

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

Емпирично изследване е изследване, при което се установява наличието на факти чрез опит в практиката.

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

Пример 1: изчисляване стойност на елемент/сума на аритметична/геометрична прогресия.

Пример 2: В практиката при изчисляване обем на конус се използва директно познатата формула. Тя естествено е вече доказана чрез използване на редица от кръгови цилиндри с различни диаметри. Аналогичен е случая за извеждане формулата за обем на пирамида  - при доказателството са използвани ред от призми.

Пример 3: Квадрат с дължина на страната N е разделен на множество еднакви, по-малки квадрати, всеки с дължина на страната 1. Да се изчисли броя квадратчета, през които минават двата основни диагонала. Емпирична формула ни дава директно резултата k = 2*N - N%2.

В следващия пример (триъгълни числа) неявно се търси сума на елементи в аритметична прогресия. Крайният резултат се получава чрез две аналогични функции - рекурсия и итерация. Приложен е сорс код:triygylni-chisla:

Правоъгълно число се нарича такова естествено число, което е член на редицата, дефинирана като произведения на две последователни естествени числа. По дефиниция "n"-тото по ред правоъгълно число е двойно по-голямо от n-тото триъгълно число. Първите няколко числа от редицата са: 0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, 182, 210, 240, 272, 306, 342, 380, 420, 462 …

В следващия пример (правоъгълни числа) крайният резултат се извежда чрез аналогични функции - рекурсия, итерация и емпирично. Приложен е сорс код: prawoygylni-chisla.

В горните примери наличието на рекурентна зависимост е очевидно. Но, също така очевидно се налага и извода, че рекурсия или итерация в такива случаи не са нужни. 

2. Рекурентно зададени редици

Числови редици, за които е даден първият или първите членове, както и формула, изразяваща всеки следващ член на редицата чрез предходния (предходните), се наричат рекурентно зададени редици. Във формулата следващия член на редицата може да се изрази както чрез предходния член, така и чрез номера си в редицата.

Изборът за реализация на алгоритъма трябва да бъде обоснован.

За някои от задачите рекурсията е препоръчителен избор. Пример: алгоритъм за бързо сортиране на Хоор - quicksort, Tony Hoare. Друг подобен пример: представяне на естествено десетично число в двоична бройна система.

За други задачи итерацията дава по-оптимизиран код. Пример: изчисляване на средна стойност, търсене на минимален/максимален елемент, числа на Фибоначи и др.

Често срещана задача е по дадена рекурентна зависимост да се изчисли сума от N члена и/или N-тия член на редица. 

Пример 1:

Задача от аритметична прогресия: 1, 2, 3,.....N-1, N

Формулите за :

общия (N-тия)член е An = A1 + (n-1)*d

сума на S = (A1+An)*N/2

Същата задача, но с уточнена горна граница е да се изведе сумата на естествените числа в интервала 1...100. За изчисляването на сумата не е нужен цикъл

S = (1 + 100)*100/2 = 5050 

Пример 2:

Да се изчисли сумата на дробите - елементите от редицата:

(1/(1*2)) + (1/(2*3)) + (1/(3*4))+....+ (1/((n-1)*n)

Ако внимателно се вгледаме в отделните членове бихме могли да установим следната зависимост:

(1/(1*2)) = 1/1 - 1/2

(1/(2*3)) = 1/2 - 1/3

(1/(3*4)) = 1/3 - 1/4

Така, за изчисляване на тази сума отново не е необходим цикъл. Достатъчно е само да се изчисли: 1 - 1/n = (n-1)/n

Приложеният сорс код element-w-redica изчислява търсения резултат чрез рекурсия, итерация и простичка формула. 

3. Видове цикли

Итерация (от латински iterare „повтарям“) означава повторението на даден процес или повтарящо се действие Цикличният (итеративният) изчислителен процес е многократно изпълнение на определена последователност от операции с данни. Данните могат да бъдат от вече съществуваща последователност (файл, константен масив и др.) или да се въвеждат. Циклите могат да бъдат с пред или пост условие и задължително в тялото на цикъла се променя поне една величина - параметъра на цикъла.

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

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

Видове цикли:

for: при предварително ясен брой итерации;

while: въвежда се условие след изпълнението на което, цикълът се прекратява;

do – while: подобни са на цикъл while,  винаги се извършва една итерация, едва след което се проверява дали условието за приключване на цикъла е валидно;

For each: използват се основно за обхождането на (динамичен/статичен) масив от елементи/обекти.

Следващият пример по същество обединява две често срещани задачи.

да се определи броят на цифрите на въведено естествено число;

да се изчисли сумата от цифрите на въведено естествено число;

Пример за сравняване итерация и рекурсия е приложения сорс код cifri-na-chislo, който реализира описаните по-горе задачи. 

4. Видове рекурсия

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

Последователността от извиквания при косвената рекурсия може да бъде различно. Пример при наличие на едно условие се извиква една функция, а при различно - друга, но цикълът винаги се затваря.

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

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

Приложеният сорс код opashata-rekursiq дава пример за опашата рекурсия.

 единична и множествена рекурсия

Рекурсия, която съдържа само едно извикване се нарича единична рекурсия, а рекурсия, при която е налице многократно извикване се нарича множествена рекурсия.

Пример за множествена рекурсия е функцията на Акерман, която се описва по следния начин:

A(m,n) = n+1   if m=0;

A(m,n) = A(m-1,1  if m>0 and n=0;

A(m,n) = A(m-1, A(m,n-1))    if m>0 and n>0;

Приложеният сорс код funkciq-na-Akkerman използва аналогични функции, съдържащи итерация и единична рекурсия и множествена рекурсия:

Други примери за множествена рекурсия са: при изчисляване числа на Фибоначи, при извеждане на числов триъгълник и др.

 5. Често срещани грешки

Възможни грешки:

от използвания алгоритъм. Пример изчисляване число на Непер, число на Лудолф и др.

недостатъчна точност вследствие на хардуерни ограничения: малко свободна RAM памет и/или използване на рекурсия с много обръщения.

Изборът на вида (итерация или рекурсия) реализация трябва да бъде добре аргументиран: сложност на алгоритъма, време за работа, сложност на кода, време за реализация и др. Приложеният сорс код wreme-za-rabota дава възможност за приблизителна оценка на необходимото време за работа.

Преди програмиста да започне писането на код, проектантът трябва да е проверил/доказал дали задачата е решима с оглед допустимо време и налична памет.

Пример за нерешима задача е Великата теорема на Ферма (формулирана 1637, доказана 1994 от Ендрю Уайлс) - търсене на такава четворка естествени числа n,a,b,c даваща решение на уравнението:

a^n + b^n = c^n за n>2

Отговорът a = b = c = 0 не налага използване на ресурс, но и едва ли е практически приложим. При n=2 отговорът е питагорова тройка. 

Съберете допълнително информация за: рекурсивни функции.