Algorytm rekursywny: opis, analiza, opis i przykłady

Nowoczesne rozumienie rekurencji: definicja funkcji i odwołania do niej z zewnątrz i z tej funkcjonalności. Uważa się, że rekursja została stworzona matematyka: obliczanie silni, niekończące się szeregi, fraktale, ciągłe ułamki... Jednak rekursji można znaleźć wszędzie. Obiektywne naturalne prawa «wierzy» rekursji swoim podstawowym algorytmem i formą wyrażenia (istnienia) nie tyle przedmiotów świata materialnego, o ile w ogóle podstawowym algorytmem ruchu.

Ludzie różnych specjalności w różnych dziedzinach nauki i techniki używają rekursywny algorytm f (x), gdzie „x ~/= f (x)». Funkcja, która sama siebie, - silne rozwiązanie, ale kształtowanie i zrozumienie tego rozwiązania, w większości przypadków, bardzo trudne zadanie.

W dawnych czasach stosowano rekursji dla zwiększenia pałacowego przestrzeni. Poprzez system skierowanych na siebie luster, można stworzyć wspaniałe trójwymiarowe efekty przestrzenne. Ale czy tak łatwo zrozumieć, jak skonfigurować te lusterka? A jeszcze bardziej trudno jest określić, gdzie znajduje się punkt w przestrzeni, odparta przez kilka luster.

Rekursja, rekurencyjne algorytmy: sens i składnia

Zadanie, które jest sformułowane powtórzeniem sekwencji operacji może być rozwiązany rekurencyjnie. Prosty algorytm (obliczenie równania kwadratowego, skrypt napełniania strony internetowej, informacji, czytanie pliku, wysyłanie wiadomości...) nie wymaga stosowania rekurencji.

Podstawowe różnice algorytmu, który pozwala na rekurencyjne rozwiązanie:

• Istnieje algorytm, który trzeba wykonać kilka razy;
• łódź potrzebuje danych, które zmieniają się za każdym razem;
• łódź nie musi się zmieniać za każdym razem;
• Jest warunek końcowy: algorytm rekursywny - nie ma końca.

W żadnym wypadku nie można twierdzić, że однократность wykonania - warunek braku powodu do rekurencji. Nie można również wymagać posiadania obowiązkowego końcowego warunki: u nieskończonych рекурсий ma swój zakres stosowania.

Bardziej:

Główne etapy rozwoju psychiki w филогенезе

Rozwój psychiki w филогенезе charakteryzuje się kilkoma etapami. Rozważmy dwie główne historie związane z tym procesem.Филогенез - to historyczny rozwój, obejmującego miliony lat ewolucji, historię rozwoju różnych gatunków organizmów żywych.Ontogenez...

Co to jest gronkowiec i metody jego leczenia

Wielu w swoim życiu miał do czynienia z zakażeniem gronkowca. Dlatego konieczne jest posiadanie pełnej informacji o tej chorobie, aby w pełni zrozumieć, co dzieje się w organizmie. Więc co to jest gronkowiec? To bakterie, lub jedną z ich odmian, z kt...

Co studiuje morfologia

 Przed podjęciem się, że studiuje morfologia, należy zauważyć, że sam studiuje ten dział gramatyki. Tak, morfologia studiuje słowo jako część mowy, a także sposoby jego edukacji, jego formy, struktury i gramatyki wartości, a także poszczególne j...

Algorytm rekursywny: gdy sekwencja operacji jest wykonywana wielokrotnie, na danych, które zmieniają się za każdym razem i dając za każdym razem nowy wynik.

Formuła rekurencji

Matematyczne rozumienie rekurencji i jej odpowiednik w programowaniu odmienny. Matematyki, choć są charakterystyczne objawy programowania, ale programowanie to matematyka jest znacznie wyższego rzędu.

Dobrze napisany algorytm - jak lustro inteligencji autora. Ogólna formuła rekurencji w programowaniu «f (x)», gdzie „x ~/= f (x)» ma co najmniej dwa warianty interpretacji. Tutaj «~» - podobieństwo lub brak rezultatów, a «=» - obecność wynik funkcji.

Pierwsza opcja: dynamika danych.

• Funkcja «f(x)» ma algorytm rekursywny i nie zmienny;
• „x” w i wynik óf(x)» - za każdym razem są nowe wartości, wynik óf(x)» jest nowym parametrem „x” tej funkcji.

Druga opcja: dynamika kodu.

• Funkcja «f(x)» ma kilka algorytmów, wyrafinowane (analizy danych);
• Analiza danych - jedna część kodu i realizacja rekurencyjnych algorytmów realizujących akcję, - druga część kodu;
• Wynik funkcji «f(x)» - nie.

Brak rezultatów - to normalne zjawisko. Programowanie to nie matematyka, tu wynik nie koniecznie musi się znajdować wyraźnie. Funkcja wykonywalny rekurencyjnie, może po prostu zrobić analizowania stron i wypełnić bazę danych, lub tworzyć żądaną instancje obiektów zgodnie z kandydatowi wejściowego strumienia.

Dane i rekursja

Programowanie algorytmów rekurencyjnych - nie jest to obliczenie silni, w którym funkcja otrzymuje za każdym razem ta, doskonała na jednostkę w dół lub w górę - wariant realizacji zależy od preferencji programisty.

Nie ma znaczenia, jak liczyć silnia «8!», poruszając się od 0, 1, 2, ... lub odwrotnie, 8, 7, 6 ... Podobnie jak obliczenia matematyczne sekwencji, fraktali lub nieskończonego szeregu zapisywany jest prosty matematycznej formuły i, odpowiednio, algorytmem, który ściśle przestrzega tej formule.

Przetwarzanie informacji - to «matematyka» zupełnie innego rzędu. Funkcje rekurencyjne i algorytmy tutaj działają literami, słowami, słowami, zdaniami i akapitami. Każdy następny poziom używa poprzedniego.

Wejściowy strumień danych jest analizowany w szerokim zakresie warunków, ale proces analizy w ogóle рекурсивен. Nie ma sensu pisać unikalne algorytmy na wszystkie opcje strumienia wejściowego. Powinien być jeden funkcjonalność. Tutaj algorytmy rekurencyjne przykłady tego, jak kształtować strumień wyjściowy odpowiedniego wejścia. To nie jest wynik, przychodzący na wejście rekurencyjnego algorytmu, ale to pożądane i potrzebne rozwiązanie.

Abstrakcja, rekursja i OOP

Programowanie zorientowane Obiektowo (OOP) i rekursja - diametralnie różne istoty, ale idealnie się uzupełniają. Abstrakcja nie ma nic wspólnego z rekurencji, ale przez pryzmat OOP stwarza możliwość realizacji partnerskiej rekurencji.

Na Przykład, idzie analizy informacji i Wyróżniają się Osobno litery, słowa, frazy, zdania i akapity. Oczywiście wywoływacz предусмотрит tworzenie instancji obiektów tych pięciu typów i zaproponuje Rozwiązanie rekurencyjnych algorytmów na każdym poziomie.

Tymczasem, jeśli na poziomie liter «nie ma sensu szukać sensu», na poziomie słów pojawia się semantyka. Można podzielić słowa na czasowniki, rzeczowniki, przysłówki, przyimki ... Można pójść dalej i określić przypadki.

Na poziomie zwrotów semantyka uzupełnione znakami interpunkcji i logiki kombinacji słów. Na poziomie zdań jest wykrywany bardziej doskonały poziom semantyki, a akapit można traktować jak zakończonym myśl.

Obiektowe projektowanie przesądza o dziedziczenie właściwości i metod i oferuje rozwijać hierarchię obiektów z tworzenia zupełnie abstrakcyjnego przodka. Przy tym, bez wątpienia, analiza każdego potomka będzie mieć charakter rekursywny i nie zbyt się różnić na poziomie technicznym w wielu pozycjach (litery, słowa, zwroty i zdania). Akapity, jak kończyć myśli, mogą wyróżniać się z tej listy, ale nie o to chodzi.

Ważne jest, że większość algorytmu można sformułować na poziomie abstrakcyjnego przodka, wymieniając jej na poziomie każdego potomka danymi i metodami, вызываемыми z abstrakcyjnego poziomu. W tym kontekście abstrakcja otwiera nowe horyzonty dla rekurencji.

Historyczne cechy OOP

OOP przyszło na świat programów dwukrotnie, chociaż niektórzy eksperci mogą przeznaczyć pojawienie się technologii cloud i współczesne wyobrażenia o obiektach i klasach, jako nowy etap w rozwoju technologii IT.

Terminy ów, obiekt» i «przejrzyste» w dzisiejszym kontekście OOP, są zwykle przypisane do 50. i 60. lat ubiegłego wieku, ale łączyła ich z 1965 roku i pojawieniem się języka Simula, Lisp, Algol, Smalltalk.

W tamtych czasach programowanie nie różniło się specjalnie rozwojem i nie może odpowiednio reagować na rewolucyjne koncepcje. Do walki pomysłów i stylów programowania (C/C++ i Pascal - w zasadzie) jeszcze było daleko, a bazy danych dopiero formowały się koncepcyjnie.

W końcu lat 80-tych i początku 90-tych w Pascal pojawiły się obiekty i wszyscy przypomnieli sobie o klasach w c/C++ - był to nowy etap zainteresowania OOP i wtedy właśnie narzędzia, przede wszystkim języki programowania stały się nie tylko utrzymać obiektowe pomysły, ale i rozwijać się odpowiednio do nich.

Oczywiście, jeśli wcześniej rekurencyjne algorytmy stanowiły tylko funkcje użyte w sumie kodzie programu, to teraz rekursja mogła stać się częścią właściwości obiektu (klasy), co w kontekście dziedziczenia daje ciekawe możliwości.

Cechą współczesnego OOP

Rozwój OOP początkowo deklarowało obiekty (klasy) jako zbiory danych i właściwości (metod). W rzeczywistości chodziło o danych, które mają składnia i sens. Ale wtedy nie udało się przedstawić OOP, jako narzędzie zarządzania rzeczywistymi obiektami.

OOP przekształcił się w narzędzie do zarządzania obiektami «komputerowej natury”. Skrypt, przycisk, menu, pasek menu, tag w tym samym okienku przeglądarki - to obiekt. Ale nie maszyna, produkt żywnościowy, słowo, lub zdanie. Prawdziwe obiekty pozostały poza programowania obiektowego, a narzędzia komputerowe zakupione nowe wcielenie.

Z Powodu różnic popularnych języków programowania, pojawiło się wiele dialektów OOP. W semantyki są praktycznie równoważne, a ich orientacja na sferę instrumentalną, a nie stosować, umożliwia znieść opis rzeczywistych obiektów poza algorytmów i zapewniać ich межплатформенное i межъязыковое «istnienie”.

Stosy i mechanizmy wywoływania funkcji

Mechanizmy wywołania funkcji (procedur, algorytmów) wymagają przesyłania danych (parametrów), zwrot rezultatu i zapamiętywanie adresu operatora, który musi uzyskać sterowanie po zakończeniu funkcji (procedury).

Zwykle do tych celów służy stos, choć języki programowania lub sam programista, programista może przewidzieć różne warianty transmisji sterowania. Nowoczesne programowanie przyznaje, że nazwa funkcji może być nie tylko parametrem: może kształtować się w trakcie wykonania algorytmu. Łódź może być także tworzone w trakcie wykonywania innego algorytmu.

Pojęcie rekurencyjnych algorytmów, gdy ich imiona i ciała mogą być określone w momencie edukacji zadania (do wyboru odpowiedniego algorytmu) rozszerza рекурсивность nie tylko na to, jak coś zrobić, ale ktoś to musi zrobić. Wybór algorytmu dla go «осмысленному» nazwy - obiecujące, ale stwarza trudności.

Рекурсивность na wielu funkcji

Nie można powiedzieć, że algorytm rekursywny, kiedy to powoduje siebie i tylko. Programowanie nie jest dogmat, a pojęcie рекурсивности - nie jest to jedyne wymaganie powodować się z ciała własnego algorytmu.

Praktyczne zastosowania nie zawsze dają czyste rozwiązanie. Często dane źródłowe należy gotować, a wynik rekurencyjnego wywołania należy analizować w kontekście całego zadania (algorytmu) w ogóle.

Rzeczywiście, nie tylko przed wywołaniem funkcje rekurencyjne, ale i po jej zakończeniu, może lub powinna być spowodowane przez inny program. Jeśli z wywołaniem większych problemów nie ma: rekurencyjnie funkcja A() wywołuje funkcję B(), która coś robi i powoduje, że A(), to od razu pojawia się problem ze zwrotemsterowania. Pracowała rekurencyjne wywołanie funkcji A() musi uzyskać zarządzanie, aby ponownie wywołać B(), która ponownie ją wywoła. Zwrot zarządzania, jak należy w kolejności w stosie z powrotem do B() - złą decyzję.

Programista nie jest ograniczony w wyborze ustawień i może kompletować ich nazw funkcji. Inaczej mówiąc, jest to idealne rozwiązanie przekazać w A() imię i nazwisko B() i niech sama A() sprawia, że połączenia B(). W takim wariancie nie będzie problemów ze zwrotem zarządzania, tak i realizacja rekurencyjnego algorytmu będzie bardziej przejrzyste.

Zrozumienie i poziom rekurencji

Problem rozwoju rekurencyjnych algorytmów w tym, że trzeba mieć pojęcie o dynamice procesu. Przy użyciu rekurencji w metodach obiektów, zwłaszcza na poziomie abstrakcyjnego przodka, pojawia się problem rozumienia własnego algorytmu w kontekście czasu jego wykonania.

Obecnie nie ma żadnych ograniczeń dotyczących poziomu zagnieżdżenia funkcji i pojemności stosu w mechanizmach połączeń, ale jest problem zrozumienia: w jakim momencie czasu jaki poziom danych lub jakie miejsce w klasyfikacji algorytm wykonywał wywołanie rekurencyjne funkcje i w jakiej ilości połączeń najniższej się ona znajduje.

Istniejące narzędzia debugowania często bezsilni podpowiedzieć programista właściwą decyzję.

Cykle i rekursja

Uważa się, że cykliczne wykonywanie równoważne rekurencji. Rzeczywiście, w niektórych przypadkach, rekursywny algorytm można zaimplementować w składni warunkowych i cyklicznych projektów.

Jednakże, jeśli istnieje zrozumienie, że dana funkcja powinna być zrealizowana za pomocą rekurencyjnego algorytmu, należy zrezygnować z dowolnego zewnętrznego możliwości wykorzystania pętli lub instrukcji warunkowych.

Sens polega na tym, że rekurencyjne rozwiązanie w postaci funkcji korzystającej z siebie będzie dopracowany, funkcjonalnie pełnym algorytmem. Algorytm ten wymaga od programisty wysiłku podczas jego tworzenia, rozumienia dynamiki pracy algorytmu, ale będzie to ostateczne rozwiązanie, które nie wymaga zewnętrznego sterowania.

Dowolna kombinacja zewnętrznych warunkowych i cyklicznych operatorów nie pozwoli sobie wyobrazić rekursywny algorytm w postaci pełnej gotowej funkcji.

Konsensusu rekurencji i OOP

Praktycznie we wszystkich wariantach rozwoju rekurencyjnego algorytmu powstaje plan opracować dwa algorytmu. Pierwszy algorytm tworzy listę przyszłych obiektów (wystąpień), a drugi algorytm jest właściwie rekurencyjną funkcję.

Najlepszym rozwiązaniem będzie założenie rekursji w postaci jednego właściwości (metody), w rzeczywistości zawiera rekursywny algorytm, a wszystkie prace przygotowawcze idą do konstruktora obiektu.

Rekursywny algorytm będzie tylko wtedy dobrym rozwiązaniem, gdy pracuje tylko sam, bez zewnętrznej kontroli i sterowania. Zewnętrzny łódź może tylko dać sygnał do pracy. Wynikiem tej pracy powinno być oczekiwane rozwiązanie, bez wsparcia z zewnątrz.

Rekursja zawsze musi być dopracowany samodzielnym rozwiązaniem.

Intuicyjne zrozumienie i funkcjonalna pełnia

Gdy programowanie zorientowane obiektowo stał się de facto standardem, stało się oczywiste: dla efektywnego kodowania należy zmienić własne myślenie. Programista musi przejść od składni i semantyki języka do dynamiki semantyki w trakcie wykonania algorytmu.

Cechą Charakterystyczną rekurencji: może być stosowany we wszystkich:

• Analizowania stron internetowych;
• Operacje wyszukiwania;
• Sortowanie informacji tekstowych;
• Czytanie i tworzenie dokumentów MS Word;
• Próbka lub analiza tagów...

Cechą Charakterystyczną OOP: ja daje możliwość opisać rekursywny algorytm na poziomie abstrakcyjnego przodka, ale przewidzieć w nim apel do unikalnym potomków, z których każdy posiada własną paletę danych i właściwości.

Rekursja - idealna, ponieważ wymaga funkcjonalnej kompletności swojego algorytmu. OOP poprawia wskaźniki jakościowe rekurencyjnego algorytmu, dając mu dostęp do wszystkich wyjątkowy potomkom.