Рекурсия

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

В програмирането с рекурсия се обозначава случай, когато една подпрограма вика предходна своя функция. Рекурсията условно се разделя в две категории: директна (пряка) и индиректна (косвена). Рекурсията е пряка, когато в тялото на подпрограмата има референция към нея. Косвена е тази рекурсия, при която една подпрограма вика друга, а тя вика предходната. Съществуват и случаи на косвена рекурсия, при които подпрограмата извиква себе си, след поредица от обръщения към други подпрограми.

Дефиниция[редактиране | редактиране на кода]

Рекурсия[1][редактиране | редактиране на кода]

Произход - от лат. recurrere. Програмна техника, която включва в себе си използването на процедури, подпрограми, функции или алгоритми, които извикват свои опростени версии един или повече пъти, при решаването на определен проблем (докато дадено условие е изпълнено), през което време резултатът от всяко повторение се изпълнява от последното извикано повторение в посока първото.

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

Рекурсивен[2][редактиране | редактиране на кода]

Характеризира повтаряемост, по-конкретно:

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

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

Повече за рекурсията[редактиране | редактиране на кода]

Матрьошки една в друга.

Рекурсията в програмирането обикновено се обяснява с практически реализации в съответния език за програмиране. Тези примери, макар да онагледяват достатъчно добре принципа на действие, често не предават по най-добрия възможен начин какво всъщност представлява. В по-общ смисъл, ако се излезе отвъд рамките на използвания синтаксис, чисто концептуално рекурсията може да бъде оприличена на играчката матрьошка. В конкретния пример началото на рекурсията е първоначалното състояние на играчката – една голяма кукла. При отваряне, вътре се намира по-малка версия на куклата, после още по-малка версия и така n на брой пъти, докато се стигне до т.нар. дъно на рекурсията, представляващо най-малкото копие на същата кукла, която не може да бъде отворена или манипулирана по някакъв начин. Винаги, когато се използва рекурсия едно от първите неща, които трябва да се вземат в предвид е: кога ще бъде достигнато дъното й. Както всеки цикъл има условия, при които спира, така и всяка рекурсия трябва да има такива. В противен случай ще се стигне до грешка от типа на "Stack overflow exception", или "препълване на стека". Това е една от най-честите грешки, които програмистите допускат.

На пръв поглед рекурсията изглежда парадоксално, поради впечатлението, че при приложението ѝ, обектът бива дефиниран чрез самия обект. Логически погледнато, това би довело до безкрайна цикличност. В действителност при практическото приложение на рекурсия обектът не бива дефиниран чрез себе си, а по-прости свои версии. Връщайки се към аналогията с матрьошките, при отваряне на голямата матрьошка, резултатът е по-опростено копие на същата матрьошка, до достигане на най-малкото нейно копие, опростено до такава степен, че не подлежи на последваща манипулация. Т.е. рекурсивното дефиниране на обект е извикване на неговата опростена версия.

Съществуват различни подходи за онагледяването на рекурсивно извикване, но тук ще бъдат разгледани по-конкретно два вида: чрез стек и дърво. В пета глава на книгата си „An Eternal Golden Braid“[3] Дъглас Хофстетър прилага различни примери, за да онагледи термина рекурсия. По-специално фокусът е върху върху неговата аналогия на рекурсия, в контекста на понятието стек. Авторският пример проследява служител на компания, който разговаря по своя телефон с потребител А, когато друг потребител Б се обажда в същия момент. Служителят слага А на изчакване и се фокусира върху Б, докато не получи трето обаждане от потребител В. Потребител Б е сложен на изчакване, докато не приключи разговора с потребител В. После служителят се връща към Б, докато не се появи четвърти потребител Г. След приключване на последния разговор служителят може да се върне към потребител Б и в последствие към А. Тази базова аналогия от ежедневието демонстрира рекурсивно поведение в стек, където всеки последващ елемент бива добавен и респективно изваждан от стека. Това са понятията „push“ и „pop“. В примера на Хофстетър „push“ обозначава спирането на конкретната операция, запомнянето на състоянието ѝ и поемането на нова задача, която стои на по-ниско ниво. „Pop“ извършва обратният процес, а именно затварянето на операцията на по-ниско ниво и връщането към предходната, която е с едно ниво нагоре.

Гореописаният процес е ясно различим при обхождане на дърво. За целта ще бъде приложен превод на извадка от обяснение в следната темa[4] от сайта http://stackoverflow.com/. В компютърните науки дървото е множество от разклонения, които са свързани помежду си. Тези разклонения може да имат едно или повече дъщерни разклонения. Всяко отделно разклонение се обозначава като връх, към който сочи един път. Този път се нарича още ребро. Празното множество е известно като нулев граф. В конкретния пример всеки от върховете на дървото има определена числова стойност, а целта е да се намери сумата от всички върхове в дървото. За да се извърши тази операция ще бъде приложено рекурсивно извикване на върха и неговите дъщерни разклонения чрез следния код, реализиран на езика C#:

class Node
{
    public Node Left { get; set; }
    public Node Right { get; set; }

    public int Value { get; set; }

    public Node(int value)
    {
        this.Value = value;
    }
}

class Program
{
    static int SumNodes(Node root)
    {
        // Ако коренът има нулева стойност (нулев граф) тогава нямаме дърво
        if (root == null)
        {
            return 0;
        }
        // В случай, че стойността на корена е различна от 0 имаме дърво
        int sum = checked(root.Value + SumNodes(root.Left) + SumNodes(root.Right));
        return sum;
    }

    static void Main()
    {
        Node root = new Node(5)
        {
            Left = new Node(4)
            {
                Left = new Node(2),
                Right = new Node(1)
            },
            Right = new Node(3)
        };

        int sum = SumNodes(root);
        Console.WriteLine(sum); // 15
    }
}

Долната схема представя примерното дърво, където цифрите са стойност на връх, / и \ обозначават ребрата, а @ - нулев граф:

    5
   / \
  4   3
 /\   /\
2  1  @ @
/\  /\
@ @ @ @

При прилагане на метода SumNodes върху корена 5 , се получава следното:

return корена->стойност + SumNodes (корен->ляв връх) + SumNodes (корен->десен връх) ;
return 5 + SumNodes (връх със стойност 4) + SumNodes (връх със стойност 3) ;

На всяка стъпка, изписването се разширява със съдържанието на съотверния return. Получава се следното:

return 5 + 4 + SumNodes (връх със стойност 2) + SumNodes (връх със стойност 1)
 + SumNodes (връх със стойност 3) ;
return 5 + 4
 + 2 + SumNodes (нулев граф) + SumNodes (нулев граф)
 + SumNodes (връх със стойност 1)
 + SumNodes (връх със стойност 3) ;
return 5 + 4
 + 2 + 0 + 0
+ SumNodes (връх със стойност 1)
 + SumNodes (връх със стойност 3) ;
return 5 + 4
 + 2 + 0 + 0
 + 1 + SumNodes (нулев граф) + SumNodes (нулев граф)
 + SumNodes (връх със стойност 3) ;
return 5 + 4
 + 2 + 0 + 0
 + 1 + 0 + 0
+ SumNodes (връх със стойност 3) ;
return 5 + 4
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + SumNodes (нулев граф) + SumNodes (нулев граф);
return 5 + 4
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + 0 + 0 ;
return 5 + 4
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 ;
return 5 + 4
 + 2 + 0 + 0
 + 1
 + 3  ;
return 5 + 4
 + 2
 + 1
 + 3  ;
return 5 + 4
 + 3
 + 3  ;
return 5 + 7
 + 3  ;
return 5 + 10 ;
return 15 ;

Крайната сума, получена чрез прилагането на рекурсия е 15.

Видове рекурсия[редактиране | редактиране на кода]

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

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

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

Множествената рекурсия може да бъде сведена до единична (респективно преобразувана в итерация). Например, при изчисление на поредицата на Фибоначи, действието може да бъде сведено до единична рекурсия чрез подаването на две последователни стойности като параметри. Това се нарича двойна рекурсия (corecursion), при която на всяка стъпка се подават два параметъра.

Косвена рекурсия[редактиране | редактиране на кода]

Най-разпространените примери за рекурсия демонстрират пряка рекурсия, при която извикването е директно. За да e налице случай на косвена рекурсия е необходимо извикване от друга функция(изрично или имплицитно). Например, ако при прилагането на рекурсивен подход f извиква f, се касае за случай на пряка рекурсия, но ако f извиква g, който от своя страна вика f, тогава има налице косвена рекурсия на f. Срещат се и случаи на верижни (три или повече) функционални извиквания; например, функция 1 извиква функция 2, функция 2 извиква функция 3, и функция 3 извиква отново функция 1.

Когато в тялото на метод се извършва извикване на същия метод, методът се дефинира като пряко рекурсивен. Ако метод A се обръща към метод B, B към C, а С отново към А, се твърди, че методът А, както и методите В и C са косвено рекурсивни или взаимно рекурсивни.

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

Косвената рекурсия понякога се наименова споделена рекурсия (mutual recursion), термин, при който фокусът е върху гледната точка, а не идеята. Например, когато f извиква g и след това g извиква f, който от своя страна отново извиква g, погледнато от гледна точка на f, f е индиректно рекурсивна, идентично - от гледна точка на g, отново се касае за косвена рекурсия, докато от гледна точка на двете, f и g са взаимно рекурсивни. Идентично, когато налице са три или повече функции, извикващи се взаимно, те могат да бъдат наречени множество от взаимно рекурсивни функции.

Анонимна рекурсия[редактиране | редактиране на кода]

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

В компютърните науки, анонимната рекурсия е рекурсия, която не вика изрично функцията по име, а по-скоро имплицитно я призовава в зависимост от текущия контекст. Това се реализира в някои програмни езици чрез ключове (или други конструкции), които позволяват референция.

Приложение[редактиране | редактиране на кода]

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

Анонимната рекурсия главно се изразява в извикване на текущата функция, което резултира в пряка рекурсия. Анонимна косвена рекурсия е възможна при извикване на предходна функция, или по-рядко при връщане към по-горна функция в стека. Това самоизвикване на текущата функция е функционален еквивалент на ключовата дума „this“ в обектно-ориентираното програмиране, позволяващо референция в текущия контекст.

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

Структурна и генеративна рекурсия[редактиране | редактиране на кода]

Някои автори класифицират рекурсията като „структурна" или „генеративна”. Разликата се корени в това, от къде рекурсивното извикване получава данните, с които оперира, и начинът, по който ги обработва.

Функции, които използват списъчни данни, обикновено разделят аргументите на техните преки структурни компоненти и впоследствие ги обработват. Ако някой от тях е от същия тип като входния, функцията е рекурсивна. Поради тази причина, тези функции се определят като (структурно) рекурсивни.

На база гореспоменатото може да се стигне до заключението, че определящата характеристика на структурно рекурсивната функция, а именно аргументът на всяко рекурсивно извикване, е съдържанието на поле от първоизточника. Към структурната рекурсия могат да бъдат отнесени почти всички обхождания на дървета, включително XML обработка, създаване и търсене в двоични дървета, и т.н. Вземайки в предвид алгебричната структура на естествените числа (естествено число е или нула, или наследник на естествено число), функции като факториел могат да се разглеждат като структурни рекурсии.

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

Разграничението на структурна и генеративна рекурсия е важно, за да се осигури условие за прекратяване на функцията. Всички структурно рекурсивни функции са ограничени (по тип) структури от данни и могат лесно да бъдат прекратени чрез структурна индукция: всяко рекурсивно извикване получава опростена част от входните данни, до достигане на базовия случай (дъно на рекурсията). В противовес, генеративно рекурсивните функции не винаги връщат опростена версия по време на рекурсивното извикване, което създава трудности при дефинирането на условието за прекратяване и предполага повече внимание при приложението им, за да се избегне бездънна рекурсия. Генеративно рекурсивните функции често могат да бъдат интерпретирани и представени като корекурсивни функции – на всяка стъпка се генерират нови данни, например при приложението на метода на Нютон – за прекратяването на корекурсията се изисква изпълнението на условие, което не винаги може да бъде осъществено.

Рекурсия и итерация - принципи, разлики[редактиране | редактиране на кода]

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

При равни други условия рекурсията е по-удачният подход когато задачата може да бъде решена с опростена версия на обекта, а итерацията се прилага в случаи, когато до крайният резултат се достига чрез определен брой повторения на обекта или повторения на операции с обекта. По-конкретно рекурсията може да бъде заменена с итерация чрез изрични стекови инструкции (например push и pop), респективно итерацията - с опашкова рекурсия. В императивното програмиране итерацията е предпочитан подход, особено в случаи на проста рекурсия, тъй като по този начин се избягва голямото процесорно натоварване, предизвиквано от множеството функционални извиквания и управлението на стековите операции. Ако налице е случай на множествена рекурсия, респективно се прилага рекурсивно извикване. Във функционалните езици, за разлика от императивното програмиране, рекурсията е предпочитан вариант, поради оптимизирания разход на процесорно време при приложението на опашкова рекурсия или при невъзможност за приложение на изрична итерация.

Съществуват две изисквания за успешно приложение на рекурсивен подход:

  • Всяко извикване трябва да опростява изчислението по някакъв начин;
  • Необходимо е наличието на специално дефинирани случаи за управлението на най-простите операции;

Принципи при приложението на итерация и рекурсия[редактиране | редактиране на кода]

  • В опростен сценарий при извикване на рекурсивен метод, методът връща резултат, който представлява базовия случай. Ако методът трябва да се справи с по-сложен проблем, то проблема бива разделен на две условни части: част, с която метода може да се справи и опростена версия на първоначалното състояние. Въпреки, че опростената версия е нова за метода, поради приликите ѝ с оригиналната версия, налице е рекурсивно извикване, с което методът решава новата версия.
  • За да приключи рекурсивното извикване, методът извиква себе си с опростена версия на първоначалното състояние, като всяко последващо опростяване трябва да произхожда от базовия случай. Когато методът разпознае базовия сценарий (най-простата версия), резултата се подава обратно към предишното извикване и чрез последователност от връщания се достига до първоначалното извикване на метода, което връща крайния резултат.
  • И двата подхода са базирани на контролни принципи: итерацията използва повторение, а рекурсията – селекция.
  • При двата подхода се осъществява повторение, като при итерация то е изрично, а рекурсията го постига чрез множество извиквания на даден метод.
  • И в двата варианта съществува условие за прекратяване: итерацията приключва, когато условието за продължение на цикъла не се изпълни, а при рекурсията – когато се достигне нейното дъно – когато метода разпознае най-простата версия на обекта.
  • Както итерацията, така и рекурсията могат да бъдат безкрайни. Когато условието за продължение на цикъла е винаги изпълнено, тогава има наличие на безкраен цикъл. За случай на безкрайна рекурсия се счита такъв, при който независимо от броя на извиквания метода не достига до най-опростената версия (базовият случай).
  • Реализацията на рекурсия изисква голям разход на процесорно време и памет, поради множественото извикване на даден метод.

Примери за рекурсия[редактиране | редактиране на кода]

Опашкова рекурсия

Опашкова рекурсия, е оптимизация, която компилаторът понякога извършва върху рекурсивен код без да ви казва за това. Ако той счете, че рекурсията е достатъчно проста (от специфичен тип) и може да я превърне в итерация, то той прави това. Така програмата намалява времето за извикване, по-ефективна откъм памет (тъй като преизползва едни и същи променливи за различните нива на рекурсията), и по-сигурна (тъй като няма шанс за stack overflow).

int foo(int ,int y)
{
   if(y == 0)
     return x;
   else
     return foo(y, x % y);
}

Акумулираща рекурсия

int foo (int n)
{
   if (n == 0)  return 1;
      return n * foo(n - 1);
}

Пряка рекурсия

int foo(int x)
{
   if (x <= 0) return x;
      return foo(x - 1);
}

Косвена рекурсия

int foo(int x)
{
   if (x <= 0) return x;
      return foo1(x);
}
int foo1(int y)
{
   return foo(y - 1);
}

Споделена рекурсия

int foo(int x)
{
   if (x <= 0) return x;
      return foo1(x);
}
int foo1(int y) {
   return foo(y - 1);
}

Нелинейна рекурсия

int foo(int n)
{
      if (n == 0) return 0;
      if (n == 1) return 1;
      return  foo(n - 1) + foo(n - 2);
}

Пример "Кулите на Ханой"

Кулите на Ханой са математически пъзел, чието решение илюстрира рекурсията. Има три колчета, които държат дискове с различни диаметри. Голям диск не може да бъде сложен върху по-малък. Започвайки от n дискове на един кол, те трябва да бъдат преместени върху друг едно по едно.Какъв е най-малкият брой стъпки, с който можем да ги преместим?

public  void move(int n, int from, int to, int via) {
   if (n == 1) {
     System.Console.WriteLine("Move disk from pole " + from + " to pole " + to);
   } else {
     move(n - 1, from, via, to);
     move(1, from, to, via);
     move(n - 1, via, to, from);
   }
 }

Пример "Двоично търсене"

Двоичното търсене е метод за намиране на елемент от подреден масив,като го разделяме на половина.На всяка стъпка от двоичното търсене ще проверявате дали на m-та позиция (където m е средата на текущо-разглеждания интервал) стои числото m. Ако не, то липсващото число е или на тази позиция, или наляво. Ако ли пък е, то значи липсващото число е на индекс, по-голям от m.

Рекурсия се използва в този алгоритъм,защото от всяка следваща стъпка се създава нов масив,като се разделя стария на половина.След това Двоичното търсене се извиква рекурсивно този път върху по-малкия масив.

public static int binarySearch(int[] array, int searchTerm, int firstIndex, int lastIndex)
{
    //Елементът не е открит, изход
    if(lastIndex < firstIndex)
    {
        return -1;
    }

    //Разделяме масива на две части и търсим само частта, от която се нуждаем
    int middle = (lastIndex + firstIndex) / 2;

    //Втората половина
    if (searchTerm > array[middle])
    {
        //Рекурсивно извикване на метода с нови индекси
        return binarySearch(array, searchTerm, middle + 1, lastIndex);
    }
    //Първата половина
    else if (searchTerm < array[middle])
    {
        // Рекурсивно извикване на метода с нови индекси
        return binarySearch(array, searchTerm, firstIndex, middle - 1);
    }
    //Елементът намерен, връщане
    return middle;
}

Рекурсия или итерация?[редактиране | редактиране на кода]

Когато алгоритъмът за решаване на даден проблем е рекурсивен, реали­зи­рането на рекурсивно решение, може да бъде много по-четливо и еле­гантно от реализирането на итеративно решение на същия проблем.

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

В определени случаи, чрез използването на рекурсия, можем да постиг­нем много по-прости, кратки и лесни за разбиране решения.

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

В дадени ситуации рекурсивните решения може да са много по-трудни за раз­би­ра­не и проследяване от съответните итеративни решения.

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

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

Примери за неправилно приложение на рекурсия[редактиране | редактиране на кода]

Типични примери за неподходящо използване на рекурсия са намирането на факториел и числата на Фибоначи.

Факториел[редактиране | редактиране на кода]

//Рекурсивно изчисляване на n!
static int FactorialRecursive(int n)
{
    if (n <= 1) return 1;
    return n * FactorialRecursive(n - 1);
}

//Итеративно изчисляване на n!
static int FactorialIterative(int n)
{
    int sum = 1;
    if (n <= 1) return sum;
    while (n > 1)
    {
        sum *= n;
        n--;
    }
    return sum;
}
N Рекурсивен Итеративен
10 334 ticks 11 ticks
100 846 ticks 23 ticks
1000 3368 ticks 110 ticks
10000 9990 ticks 975 ticks
100000 препълване на стека 9767 ticks

[5]

За измерване на времето е използван System.Diagnostics.Stopwatch, където 1 tick е 100 наносекунди.

Въпреки, че рекурсивният подход е по-кратък като код, той е много по-бавен от итеративния и е ограничен (поради препълване на стека).

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

Числа на Фибоначи[редактиране | редактиране на кода]

Още по-красноречив пример за неправилно приложение на рекурсивен подход е намиране на числа на Фибоначи.

//- Рекурсивно изчисление по стандартния алгоритъм -
static int FibonacciRecursive(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;

    return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
}

//- Рекурсивно изчисление по оптимизиран алгоритъм -
static Dictionary<int> resultHistory = new Dictionary<int>();

static int FibonacciRecursiveOpt(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (resultHistory.ContainsKey(n))
        return resultHistory[n];

    int result = FibonacciRecursiveOpt(n - 1) + FibonacciRecursiveOpt(n - 2);
    resultHistory[n] = result;

    return result;
}

// - Изчисление по итеративен подход -
static int FibonacciIterative(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;

    int prevPrev = 0;
    int prev = 1;
    int result = 0;

    for (int i = 2; i <= n; i++)
    {
        result = prev + prevPrev;
        prevPrev = prev;
        prev = result;
    }
    return result;
}
N Рекурсивен Рекурсивен оптимизиран Итеративен
5 5 ticks 22 ticks 9 ticks
10 36 ticks 49 ticks 10 ticks
20 2315 ticks 61 ticks 10 ticks
30 180254 ticks 65 ticks 10 ticks
100 препълване на стека 158 ticks 11 ticks
1000 препълване на стека 1470 ticks 27 ticks
10000 препълване на стека 13873 ticks 190 ticks
100000 препълване на стека препълване на стека 3952 ticks

И тук рекурсивният подход е много по-кратък като код, но изисква многократно повече време, за да върне очаквания резултат. Освен същите причини както при намирането на факториела, като прехвърляне на данни от едната функция към другата, тук имаме напълно излишно неколкократно изчисляване на вече изчислени членове на редицата, която расте експоненциално.

[6]

         F4
       /   \
     F3     F2
    / \    /  \
  F2  F1  F1  F0
 /  \
F1  F0

За намирането на F(4) например члена F(2) се изчислява два пъти, за намирането на F(5) трябва да се изчисли три пъти F(2) и два пъти F(3) и т.н. Колкото по-дълбока е рекурсията, толкова повече се влошава производителността.

Ако се използва оптимизираният рекурсивен алгоритъм (или динамично оптимиране, още познато като memorization), при който се съхраняват стойностите на вече намерените членове, се получават значително по-добри резултати, но не със същата ефективност като при прилагането на итеративен подход.

Имплементации базирани на рекурсия.[редактиране | редактиране на кода]

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

  • “Функции обвивки” - (Wrapper function).
  • “Даване на късо на базовия случай”, известно още като “рекурсия на една ръка разстояние”.
  • “Хибридни алгоритми”, при които се превключва към различен алгоритъм след като случаите, които се обработват намалеят достатъчно.

От гледна точка на елегантността на кода “функциите обвивки” се ползват с всеобщо одобрение, докато “даването на късо”, особено в академичните среди, се счита за по-нискокачествена техника. “Хибридните алгоритми” от своя страна често се използват за повишаване на ефективността на кода и за да се намали натоварването на рекурсията при по-малки случаи. “Рекурсията на една ръка разстояние” е частен случай на този подход.

Функция обвивка.[редактиране | редактиране на кода]

Това е функция, която се извиква пряко, но тя не се обръща рекурсивно към себе си. Вместо това "обвивката" извиква отделна, допълнителна функция, която всъщност осъществява рекурсията. “Функциите обвивки” могат да се използват за валидиране на параметри (така, че рекурсивните функции да се разтоварят от тази задача), да извършват инициализация (да разпределят памет и да инициализират променливи), това се отнася особено за спомагателни променливи като “ниво на рекурсия” или частични изчисления за меморизация (съхраняване на информация в паметта с цел по-нататъшното й използване), и да обработват изключения и грешки. В езиците, които поддържат вложени функции (nested function), спомагателната функция може да бъде вложена във “функцията обвивка” и да използва споделен обхват. При липса на вложени функции, помощните функции се използват вместо отделни такива и ако е възможно, като частни (private) функции (тъй като те не се извикват директно), и информацията се споделя с “функцията обвивка”, като се извиква по референция.

“Даване на късо на базовия случай”[редактиране | редактиране на кода]

“Даване на късо на базовия случай”, известно още като “рекурсия на една ръка разстояние”, се състои от проверка на базовия модел, преди да се направи рекурсивното извикване, т.е. проверява се дали следващото извикване ще бъде на база на случая, вместо извикване и след това проверка на базовия случай. “Даването на късо” се прилага най-вече от съображения за ефективност, за да се избегне натоварването предизвикано от извикване на функцията, което се връща незабавно. Трябва да се вземе в предвид, че тъй като базовият случай вече е бил проверен (непосредствено преди рекурсивната стъпка), няма нужда да се проверява отделно, но трябва да се използва функция обвивка при случаите, когато самата рекурсия започва с базовия случай. Примерно, при изчисляването на факториал стандартният ред за базовия случай е: 0! = 1, но в алгоритъма за 1! веднага се връща 1, това е “даване на късо” и на практика може да се пропусне достигането до нулата. Това може да се облекчи чрез използването на “функция обвивка”.

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

Хибриден алгоритъм[редактиране | редактиране на кода]

Рекурсивните алгоритми често са неефективни при малки обеми данни, поради натоварването предизвикано от многократните извиквания на функцията и връщането на резултат. По тази причина ефективните реализации на рекурсивни алгоритми често започват с рекурсия, но след това преминават към по-различен алгоритъм, когато обработваните данни намалеят. Пример за това е сортирането чрез сливане, което често се осъществява чрез преминаване към нерекусивно сортиране чрез вмъкване (insertion sort), когато данните са достатъчно малки. Хибридните рекурсивни алгоритми често могат да бъдат усъвършенствани.

Източници[редактиране | редактиране на кода]

  1. ((en))  Definition of recursion. // Merriam-Webster. Посетен на 30.08.2013 г..
  2. ((en))  Definition of recursive in English. // Oxford University Press. Посетен на 30.08.2013 г..
  3. Hofstadter, Douglas R. Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books, 1999. ISBN 978-0-465-02656-2, ISBN 0-14-017997-6. с. 777.
  4. ((en))  Understanding recursion. // Посетен на 30.08.2013 г..
  5. Lantzman, Eyal. Iterative vs. Recursive Approaches. 2007.
  6. Наков, Преслав и др. Програмиране=++Алгоритми;. 2012. с. Глава 1.2 Рекурсия и итерация.