Алгоритъм рекурсивен: описание, анализ, характеристики и примери

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

Хора от различни специалности в различни области на науката и технологиите използват рекурсивния алгоритъм f (x), където "x ~ / = f (x)". Функция, която се нарича себе си, е силно решение, но формирането и разбирането на това решение в повечето случаи е много трудна задача.

В древни времена рекурсията се използва за увеличаване на пространството на двореца. Чрез система от огледала, които са обърнати един към друг, можете да създадете зашеметяващи обемен пространствен ефект. Но лесно ли е да разберете как да настроите тези огледала? И е още по-трудно да се определи къде се намира точката в пространството, отразена чрез няколко огледала.

Рекурсивно, рекурсивно алгоритми: смисъл и синтаксис

Задача, формулирана чрез повтаряне на последователност от операции, може да бъде решен рекурсивно. Един прост алгоритъм (изчисляване на квадратично уравнение, скрипт за попълване на уеб страница с информация, четене на файл, изпращане на съобщение ...) не изисква използването на рекурсия.

Основните разлики в алгоритъма, който позволява рекурсивно решение:

• има алгоритъм, който трябва да бъде изпълнен няколко пъти;
• алгоритъмът се нуждае от данни, които се променят всеки път;
• Алгоритъмът не трябва да се променя всеки път;
• има крайно условие: алгоритъмът е рекурсивен - не безкраен.

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

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

Рекурсивната формула

Математическото разбиране на рекурсията и нейния аналог в програмирането са различни. Математиката, макар и характерна за програмирането, но програмирането е много по-висока математика.

Добре написан алгоритъм е като огледало на интелекта на автора. Общата формула за рекурсия при програмиране "f (x)", където "x ~ / = f (x)" има най-малко два варианта на интерпретация. Тук "~" е сходството или отсъствието на резултата, а "=" е присъствието на резултата от функцията.

Първият вариант е динамиката на данните.

• функция "f (x)" има алгоритъм рекурсивен и не променлива;
• "X" и резултатът "f (x)" - всеки път имат нови стойности, резултатът "f (x)" е нов параметър "x" на тази функция.

Вторият вариант: динамиката на кода.

• функцията "f (x)" има няколко алгоритми, които усъвършенстват (анализират) данните;
• анализ на данните - една част от кода и внедряване на рекурсивни алгоритми, които изпълняват желаното действие - втората част на кода;
• резултатът от функцията "f (x)" не е такъв.

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

Данни и рекурсия

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

Няма значение като счита факторен "8!", Преместване от 0, 1, 2, ..., или обратно 8, 7, 6 ... По същия начин изчисляване математическа последователност, фрактален или безкрайна серия се записва, и проста математическа формула, съответно, алгоритъм, който стриктно следва тази формула.

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

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

Абстракция, рекурсия и ООП

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

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

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

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

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

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

Исторически характеристики на ООП

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

Терминът "обект" и "обект" в настоящия контекст на ООП, обикновено приписвани на 50-те и 60-те години на миналия век, но ги свързват с 1965 г. и появата на Simula език, Lisp, Алгол, Smalltalk.

В онези дни програмирането не беше много специално и не можеше да отговори адекватно на революционните концепции. Преди борбата за идеи и стилове на програмиране (C / C ++ и Pascal - най-вече) тя все още е далече и базите данни все още се формират концептуално.

В края на 80-те и началото на 90-те Паскал появи обекти и всички мисли от класовете в C / C ++ - той отбеляза нов кръг от интерес за освобождение на Палестина, и това е, когато инструментите, особено езици за програмиране са станали не само подкрепа обектно-ориентираното идеи, но също така се развиват според тях.

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

Характеристика на модерните OOP

Развитието на ООП първоначално декларира обекти (класове) като набор от данни и свойства (методи). Всъщност става въпрос за данни със синтаксис и смисъл. Но тогава не беше възможно да се представи ООП като инструмент за управление на реални обекти.

ООП се превърна в инструмент за управление на обекти от "компютърна природа". Скрипт, бутон, елемент от менюто, лента с менюта, маркер в прозореца на браузъра е обект. Но не и машинен инструмент, хранителен продукт, дума или оферта. Истинските обекти останаха извън обхвата на обектно-ориентираното програмиране, а компютърните инструменти придобиха ново въплъщение.

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

Стакове и механизми за призоваване на функции

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

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

Идеята на рекурсивни алгоритми, когато техните имена и тялото могат да се определят в момента на задачата (изберете желания алгоритъм) recursiveness не се простира само върху това как да се направи нещо, но кой точно тя трябва да се направи. Изборът на алгоритъма за неговото "смислено" име е обещаващ, но създава трудности.

Рекурсивност на набор от функции

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

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

Всъщност, не само преди призива на рекурсивната функция, но и след нейното завършване, може да бъде или да бъде наречена друга програма. Ако няма особени проблеми с повикването: рекурсивната функция A () извиква функцията B (), която прави нещо и извиква A (), след което има проблем с връщането на контрола. След като изпълни рекурсивното повикване, функцията А () трябва да получи контрол, за да повтори B (), което ще го нарече отново. Връщане на контрола, както следва, за да се върнете в стека обратно на B () - грешното решение.

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

Разбиране и нивото на рекурсията

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

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

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

Цикли и рекурсия

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

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

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

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

Консенсус на рекурсията и ООП

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

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

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

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

Интуитивно разбиране и функционална пълнота

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

Характерна особеност на рекурсията: тя може да се приложи във всичко:

• анализ на сайтове -
• търсене операции-
• анализирайте текстовата информация -
• четене или създаване на MS Word-
• вземане на проби или анализиране на маркери ...

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

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