Рекурсия

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

ПРОЧЕТЕТЕ ПРЕДИ ТОВА:

Фракталите. Въведение

Самоподобие

Итерации

Това може да бъде и обект, който се определя като част от самия себе си.

Тези снимки изразяват смисъла на "рекурсията":

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

Рекурсията в програмирането

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

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

Един христоматиен пример за рекурсия е изчисляването на факториел на цяло неотрицателно число n! или

n!=n*(n-1)*(n-2)*...*3*2*1

За да изчислим факториел на едно число, можем в цикъл да умножим числата от 1 до n използвайки итерации.

Но може да сте забелязали, че n! е равно на n пъти (n-1)! за всяко положително число n:

n!=n*[(n-1)*(n-2)*...*3*2*1]=n*(n-1)!

Може да продължим: n!=n*(n-1)*(n-2)! ... и т.н. 

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

function factorial(n)
{if (n==1)
return 1;
return  n*factorial (n-1);}

Вижда се, че в дефиницията на функцията factorial се съдържа самата функция  factorial.

Тази, а и всяка друга задача може да се реши и с итерации, но решението с рекурсия е по-компактно и съдържа някаква красота и магия в себе си. Има еднa мисъл на Лоурънс Питър Дойч (Laurence Peter Deutsch), между другото създател на най-рекусивния език LISP: "Итерацията е човешка, рекурсията е божествена" ("To Iterate Is Human, To Recurse Divine").

Итерацията е линейна, циклична, просто постъпателно натрупване, докато рекурсията е дървовидна, тя се движи напред-назад, изкачва се - спуска се. Ето например, как изглежда рекурсивното пресмятане на n! за n=6:

Всичко в природата е рекурсивно

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

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

Продължение:

Скритите измерения на фракталната размерност

Видове фрактали

Системи Итеративни Функции (Iterated Functions System - IFS)

Алгебрични (динамични, нелинейни) фрактали

Източници:

Linear Recursion and Iteration, MIT Press

Recursion, Wolfram MathWorld