Рекурсия

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

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

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

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

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

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

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

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

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

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

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

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

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

Съществуват различни подходи за онагледяването на рекурсивно извикване, но тук ще бъдат разгледани по-конкретно два вида: чрез стек и дърво. В пета глава на книгата си „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.

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

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

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

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

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

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

Най-разпространените примери за рекурсия демонстрират пряка рекурсия, при която извикването е директно. За да 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 са взаимно рекурсивни. Идентично, когато налице са три или повече функции, извикващи се взаимно, те могат да бъдат наречени множество от взаимно рекурсивни функции.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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);
}

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

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);
   }
 }

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

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;
}

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

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

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

//Рекурсивно изчисляване на 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 междинни резултата. При итеративния подход се използва само една променлива, в която се натрупва резултатът.

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

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

//- Рекурсивно изчисление по стандартния алгоритъм -
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), при който се съхраняват стойностите на вече намерените членове, се получават значително по-добри резултати, но не със същата ефективност като при прилагането на итеративен подход.

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

  1. Definition of recursion. // Merriam-Webster. Посетен на 30.08.2013 г..
  2. 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. Understanding recursion. // Посетен на 30.08.2013 г..
  5. Lantzman, Eyal. Iterative vs. Recursive Approaches. 2007.
  6. Наков, Преслав и др. Програмиране=++Алгоритми;. 2012. с. Глава 1.2 Рекурсия и итерация.