Модерно разбиране на рекурсията: дефиниция на функционалност и достъп до нея отвън и от тази функционалност. Смята се, че рекурсията е родена от математиците: факториално изчисление, безкрайни серии, фрактали, продължителни дроби… Рекурсията обаче може да се намери навсякъде. Обективните природни закони „считат” рекурсията като основен алгоритъм и форма на изразяване (съществуване) не толкова на обектите на материалния свят, а като цяло за основния алгоритъм на движение.
Хора от различни специалности в различни области на науката и технологиите използват рекурсивния алгоритъм f (x), където "x ~/=f (x)". Функция, която извиква сама себе си, е силно решение, но формирането и разбирането на това решение в повечето случаи е много трудна задача.
В древни времена рекурсията е била използвана за увеличаване на пространството на двореца. Чрез система от огледала, насочени едно към друго, можете да създадете зашеметяващи триизмерни пространствени ефекти. Но толкова ли е лесно да се разбере какда регулирам тези огледала? Още по-трудно е да се определи къде се намира точка от пространството, отразена през няколко огледала.
Рекурсия, рекурсивни алгоритми: значение и синтаксис
Проблемът, който се формулира чрез повтаряне на последователност от операции, може да бъде решен рекурсивно. Прост алгоритъм (изчисляване на квадратно уравнение, скрипт за попълване на уеб страница с информация, четене на файл, изпращане на съобщение…) не изисква рекурсия.
Основни разлики в алгоритъма, който позволява рекурсивно решение:
- има алгоритъм, който трябва да се изпълни няколко пъти;
- алгоритъмът се нуждае от данни, които се променят всеки път;
- алгоритъмът не трябва да се променя всеки път;
- има крайно условие: алгоритъмът е рекурсивен - не е безкраен.
По принцип не може да се твърди, че еднократното изпълнение е необходимо условие за липсата на причина за рекурсия. Не можете също да изисквате задължително крайно условие: безкрайните рекурсии имат свой собствен обхват.
Алгоритъмът е рекурсивен: когато последователност от операции се изпълнява многократно, върху данни, които се променят всеки път и дава нов резултат всеки път.
Рекурсивна формула
Математическото разбиране на рекурсията и нейния аналог в програмирането са различни. Математиката, въпреки че има признаци на програмиране, но програмирането е математика от много по-висок порядък.
Добре написан алгоритъм е като огледало на интелекта на своя автор. Общформулата за рекурсия в програмирането е "f(x)", където "x ~/=f(x)" има поне две интерпретации. Тук "~" е сходството или отсъствието на резултата, а "=" е наличието на резултата от функцията.
Първа опция: динамика на данните.
- функцията "f(x)" има рекурсивен и неизменяем алгоритъм;
- "x" и резултатът "f(x)" имат нови стойности всеки път, резултатът "f(x)" е новият параметър "x" на тази функция.
Втора опция: динамика на кода.
- функцията "f(x)" има няколко алгоритма, които прецизират (анализират) данните;
- анализ на данни - една част от кода и изпълнение на рекурсивни алгоритми, които изпълняват желаното действие - втората част на кода;
- резултатът от функцията "f(x)" не е.
Няма резултат е нормално. Програмирането не е математика, тук резултатът не трябва да присъства изрично. Рекурсивна функция може просто да анализира сайтове и да попълни базата данни или да инстанцира обекти според входящия вход.
Данни и рекурсия
Програмирането на рекурсивни алгоритми не е за изчисляване на факториал, при който функцията получава всеки път дадена стойност, която е една повече или по-малко от едно - опцията за внедряване зависи от предпочитанията на разработчика.
Няма значение как е факторният "8!",алгоритъм, който стриктно следва тази формула.
Обработката на информация е "математика" от съвсем различен ред. Рекурсивните функции и алгоритми тук оперират с букви, думи, фрази, изречения и абзаци. Всяко следващо ниво използва предишното.
Входният поток от данни се анализира при широк диапазон от условия, но процесът на анализ обикновено е рекурсивен. Няма смисъл да се пишат уникални алгоритми за всички варианти на входния поток. Трябва да има една функционалност. Тук рекурсивните алгоритми са примери за това как да се формира изходен поток, който е адекватен на входа. Това не е изходът на рекурсивния алгоритъм, но е желаното и необходимо решение.
Абстракция, рекурсия и ООП
Обектно-ориентирано програмиране (ООП) и рекурсията са фундаментално различни същности, но се допълват перфектно. Абстракцията няма нищо общо с рекурсията, но през призмата на OOP създава възможност за прилагане на контекстна рекурсия.
Например, информацията се анализира и букви, думи, фрази, изречения и абзаци се подчертават отделно. Очевидно разработчикът ще осигури създаването на екземпляри на обекти от тези пет типа и ще предложи решение на рекурсивни алгоритми на всяко ниво.
Междувременно, ако на ниво букви „няма смисъл да се търси смисъл“, тогава семантиката се появява на ниво думи. Можете да разделите думите на глаголи, съществителни, наречия, предлози… Можете да отидете по-далеч и да дефинирате падежите.
На ниво фраза семантиката се допълва от препинателни знаци и логикасловосъчетания. На нивото на изреченията се открива по-съвършено ниво на семантика и параграф може да се счита за завършена мисъл.
Обектно-ориентирана разработка предопределя наследяването на свойства и методи и предлага да започне йерархията на обектите със създаването на напълно абстрактен предшественик. В същото време, без съмнение, анализът на всеки потомък ще бъде рекурсивен и няма да се различава твърде много на техническо ниво в много позиции (букви, думи, фрази и изречения). Параграфите, като пълни мисли, може да се открояват от този списък, но те не са същността.
Важно е, че преобладаващата част от алгоритъма може да бъде формулирана на ниво абстрактен предшественик, като го прецизира на нивото на всеки потомък с данни и методи, извикани от абстрактно ниво. В този контекст абстракцията отваря нови хоризонти за рекурсия.
Исторически характеристики на OOP
OOP дойде в света на софтуера два пъти, въпреки че някои експерти може да изтъкнат появата на облачните изчисления и съвременните идеи за обекти и класове като нов кръг в развитието на ИТ технологиите.
Термините "обект" и "обектив" в съвременния контекст на ООП обикновено се приписват на 50-те и 60-те години на миналия век, но те се свързват с 1965 г. и появата на Simula, Lisp, Algol, Smalltalk.
В онези дни програмирането не беше особено развито и не можеше да отговори адекватно на революционните концепции. Борбата на идеите и стиловете на програмиране (C / C ++ и Pascal - най-вече) беше все още далеч, а базите данни все още бяха концептуално оформени.
В края на 80-те и началото на 90-те години се появиха обекти в Pascal и всички си спомниха класове в C / C ++ - това отбеляза нов кръг на интерес към OOP и тогава инструментите, предимно езиците за програмиране, станаха не поддържат само обектно-ориентирани идеи, но се развиват съответно.
Разбира се, ако по-рано рекурсивните алгоритми бяха просто функции, използвани в общия код на програмата, сега рекурсията може да стане част от свойствата на обект (клас), което предоставя интересни възможности в контекста на наследяването.
Характеристика на модерния OOP
Разработването на ООП първоначално декларирани обекти (класове) като колекции от данни и свойства (методи). Всъщност ставаше дума за данни, които имат синтаксис и значение. Но тогава не беше възможно да се представи ООП като инструмент за управление на реални обекти.
OOP се превърна в инструмент за управление на обекти от "компютърна природа". Скрипт, бутон, елемент от менюто, лента с менюта, таг в прозореца на браузъра е обект. Но не машина, хранителен продукт, дума или изречение. Истинските обекти останаха извън обектно-ориентираното програмиране, а компютърните инструменти придобиха ново въплъщение.
Поради разликите в популярните езици за програмиране се появиха много диалекти на ООП. От гледна точка на семантика те са практически еквивалентни и фокусът им върху инструменталната сфера, а не върху приложната, дава възможност описанието на реалните обекти да се изведе отвъдалгоритми и гарантира тяхното междуплатформено и междуезично „съществуване“.
Стакове и механизми за извикване на функции
Механизмите за извикване на функции (процедури, алгоритми) изискват предаване на данни (параметри), връщане на резултат и запомняне на адреса на оператора, който трябва да получи управление, след като функцията (процедурата) завърши.
Обикновено стекът се използва за тази цел, въпреки че езиците за програмиране или самият разработчик могат да предоставят различни опции за прехвърляне на контрол. Съвременното програмиране признава, че името на функция може да бъде не само параметър: то може да се формира по време на изпълнението на алгоритъма. Алгоритъм може да бъде създаден и докато се изпълнява друг алгоритъм.
Концепцията за рекурсивните алгоритми, когато техните имена и тела могат да бъдат определени в момента на формиране на задачата (избиране на желания алгоритъм), разширява рекурсивността не само към това как да се направи нещо, но и кой точно трябва направи го. Изборът на алгоритъм по неговото "смислено" име е обещаващ, но създава трудности.
Рекурсивност на набор от функции
Не можете да кажете, че алгоритъмът е рекурсивен, когато се извиква и това е всичко. Програмирането не е догма и концепцията за рекурсивност не е изключително изискване да се извикате от тялото на собствения си алгоритъм.
Практическите приложения не винаги дават чисто решение. Често трябва да се подготвят първоначалните данни и резултатът от рекурсивното извикване трябва да се анализира в контекста на целия проблем (целият алгоритъм) вкато цяло.
Всъщност, не само преди да бъде извикана рекурсивна функция, но и след нейното завършване може или трябва да бъде извикана друга програма. Ако няма специални проблеми с извикването: рекурсивната функция A() извиква функцията B(), която прави нещо и извиква A(), тогава веднага възниква проблем с връщането на контрола. След като завърши рекурсивното извикване, функцията A() трябва да получи контрол, за да извика повторно B(), което ще я извика отново. Връщането на контрола, както трябва да бъде в стека обратно към B() е грешно решение.
Програмистът не е ограничен в избора на параметри и може да ги допълва с имена на функции. С други думи, идеалното решение е да предадете името на B() на A() и да оставите A() да извика B(). В този случай няма да има проблеми с връщането на контрола и изпълнението на рекурсивния алгоритъм ще бъде по-прозрачно.
Разбиране и ниво на рекурсия
Проблемът с разработването на рекурсивни алгоритми е, че трябва да разберете динамиката на процеса. Когато използвате рекурсия в обективни методи, особено на нивото на абстрактен предшественик, има проблем с разбирането на вашия собствен алгоритъм в контекста на времето за неговото изпълнение.
В момента няма ограничения за нивото на влагане на функции и капацитета на стека в механизмите за извикване, но има проблем с разбирането: в кой момент от времето кое ниво на данни или кое място в общия алгоритъм, наречен рекурсивно функция и на какъв брой обаждания е тя.
Съществуващите инструменти за отстраняване на грешки често са безсилникажете на програмиста правилното решение.
Цигли и рекурсия
Счита се, че цикличното изпълнение е еквивалентно на рекурсия. Всъщност в някои случаи рекурсивният алгоритъм може да бъде реализиран в синтаксиса на условни и циклични конструкции.
Въпреки това, ако има ясно разбиране, че определена функция трябва да се реализира чрез рекурсивен алгоритъм, всяко външно използване на цикъл или условни изрази трябва да бъде изоставено.
Смисълът тук е, че рекурсивно решение под формата на функция, използваща себе си, ще бъде пълен, функционално завършен алгоритъм. Този алгоритъм ще изисква от програмиста да го създаде с усилие, разбирайки динамиката на алгоритъма, но това ще бъде окончателното решение, което не изисква външен контрол.
Всяка комбинация от външни условни и циклични оператори няма да ни позволи да представим рекурсивния алгоритъм като пълна функция.
Консенсус за рекурсия и OOP
В почти всички варианти на разработване на рекурсивен алгоритъм възниква план за разработване на два алгоритъма. Първият алгоритъм генерира списък с бъдещи обекти (екземпляри), а вторият алгоритъм всъщност е рекурсивна функция.
Най-доброто решение би било да се организира рекурсията като едно свойство (метод), което всъщност съдържа рекурсивния алгоритъм, и да се постави цялата подготвителна работа в конструктора на обекта.
Рекурсивният алгоритъм ще бъде правилното решение само когато работисамо сам, без външен контрол и управление. Външен алгоритъм може да даде само сигнал за работа. Резултатът от тази работа трябва да бъде очакваното решение, без външна подкрепа.
Рекурсията винаги трябва да бъде цялостно самостоятелно решение.
Интуитивно разбиране и функционална пълнота
Когато обектно-ориентираното програмиране стана де факто стандарт, стана очевидно, че за да кодирате ефективно, трябва да промените собственото си мислене. Програмистът трябва да премине от синтаксиса и семантиката на езика към динамиката на семантиката по време на изпълнението на алгоритъма.
Характеристика на рекурсията: може да се приложи към всичко:
- изстъргване в мрежата;
- операции за търсене;
- разбиране на текстова информация;
- четене или създаване на MS Word документи;
- извадка или анализиране на тагове…
Характеристика на OOP: дава възможност да се опише рекурсивен алгоритъм на нивото на абстрактен предшественик, но предвижда той да се отнася до уникални потомци, всеки от които има своя собствена палитра от данни и свойства.
Рекурсията е идеална, защото изисква функционалната пълнота на своя алгоритъм. OOP подобрява производителността на рекурсивния алгоритъм, като му дава достъп до всички уникални деца.
