Nowoczesne rozumienie rekurencji: definicja funkcjonalności i dostęp do niej z zewnątrz iz tej funkcjonalności. Uważa się, że rekurencja narodziła się przez matematyków: obliczenia czynnikowe, szeregi nieskończone, fraktale, ułamki łańcuchowe … Jednak rekurencję można znaleźć wszędzie. Obiektywne prawa natury „uważają” rekurencję za swój główny algorytm i formę ekspresji (istnienia) nie tyle obiektów świata materialnego, ile ogólnie głównego algorytmu ruchu.
Ludzie różnych specjalności w różnych dziedzinach nauki i techniki używają algorytmu rekurencyjnego f (x), gdzie "x ~/=f (x)". Funkcja, która wywołuje siebie, jest silnym rozwiązaniem, ale utworzenie i zrozumienie tego rozwiązania jest w większości przypadków bardzo trudnym zadaniem.
W czasach starożytnych rekurencja była używana do zwiększania przestrzeni pałacu. Dzięki systemowi luster skierowanych na siebie można tworzyć oszałamiające trójwymiarowe efekty przestrzenne. Ale czy tak łatwo jest zrozumieć, jak?wyregulować te lusterka? Jeszcze trudniej jest określić, gdzie znajduje się punkt w przestrzeni, odbity przez kilka luster.
Rekurencja, algorytmy rekurencyjne: znaczenie i składnia
Problem sformułowany przez powtórzenie sekwencji operacji można rozwiązać rekurencyjnie. Prosty algorytm (obliczanie równania kwadratowego, skrypt wypełniający stronę internetową informacjami, odczytywanie pliku, wysyłanie wiadomości…) nie wymaga rekurencji.
Główne różnice w algorytmie umożliwiającym rozwiązanie rekurencyjne:
- istnieje algorytm, który należy wykonać kilka razy;
- algorytm potrzebuje danych, które zmieniają się za każdym razem;
- algorytm nie musi się zmieniać za każdym razem;
- istnieje warunek końcowy: algorytm jest rekurencyjny, a nie nieskończony.
Ogólnie rzecz biorąc, nie można twierdzić, że jednorazowa egzekucja jest warunkiem koniecznym braku powodu do rekurencji. Nie możesz również wymagać obowiązkowego warunku końcowego: nieskończone rekurencje mają swój własny zakres.
Algorytm jest rekurencyjny: gdy sekwencja operacji jest wykonywana wielokrotnie, na danych, które zmieniają się za każdym razem i za każdym razem dają nowy wynik.
Formuła rekurencji
Matematyczne rozumienie rekurencji i jej odpowiednika w programowaniu są różne. Matematyka, chociaż są oznaki programowania, ale programowanie to matematyka znacznie wyższego rzędu.
Dobrze napisany algorytm jest jak lustro intelektu jego autora. Ogólnyformuła rekurencji w programowaniu to „f(x)”, gdzie „x ~/=f(x)” ma co najmniej dwie interpretacje. Tutaj „~” to podobieństwo lub brak wyniku, a „=” to obecność wyniku funkcji.
Pierwsza opcja: dynamika danych.
- funkcja "f(x)" ma rekurencyjny i niezmienny algorytm;
- "x" i wynik "f(x)" mają za każdym razem nowe wartości, wynik "f(x)" jest nowym parametrem "x" tej funkcji.
Druga opcja: dynamika kodu.
- funkcja "f(x)" ma kilka algorytmów, które udoskonalają (analizują) dane;
- analiza danych - jedna część kodu i implementacja algorytmów rekurencyjnych wykonujących pożądaną akcję - druga część kodu;
- wynikiem funkcji „f(x)” nie jest.
Żaden wynik nie jest normalny. Programowanie to nie matematyka, tutaj wynik nie musi być wyraźnie obecny. Funkcja rekurencyjna może po prostu analizować witryny i wypełniać bazę danych lub tworzyć instancje obiektów zgodnie z przychodzącymi danymi wejściowymi.
Dane i rekursja
Programowanie algorytmów rekurencyjnych nie polega na obliczaniu silni, w której funkcja otrzymuje za każdym razem daną wartość o jeden większą lub mniejszą od jednego - opcja implementacji zależy od preferencji programisty.
Nie ma znaczenia, jak silnia „8!”,algorytm ściśle przestrzegający tego wzoru.
Przetwarzanie informacji to "matematyka" zupełnie innej kolejności. Funkcje i algorytmy rekurencyjne operują tutaj na literach, słowach, frazach, zdaniach i akapitach. Każdy następny poziom wykorzystuje poprzedni.
Wejściowy strumień danych jest analizowany w szerokim zakresie warunków, ale proces analizy jest na ogół rekurencyjny. Nie ma sensu pisać unikalnych algorytmów dla wszystkich wariantów strumienia wejściowego. Powinna istnieć jedna funkcjonalność. Tutaj algorytmy rekurencyjne są przykładami tworzenia strumienia wyjściowego, który jest adekwatny do danych wejściowych. Nie jest to wynik algorytmu rekurencyjnego, ale rozwiązanie pożądane i konieczne.
Abstrakcja, rekurencja i OOP
Programowanie obiektowe (OOP) i rekurencja to zasadniczo różne byty, ale doskonale się uzupełniają. Abstrakcja nie ma nic wspólnego z rekurencją, ale przez pryzmat OOP stwarza możliwość implementacji rekurencji kontekstowej.
Na przykład informacje są analizowane, a litery, słowa, frazy, zdania i akapity są podświetlane oddzielnie. Oczywiście deweloper zapewni tworzenie instancji obiektów tych pięciu typów i zaoferuje rozwiązanie algorytmów rekurencyjnych na każdym poziomie.
Tymczasem, jeśli na poziomie liter „nie ma sensu szukać znaczenia”, to semantyka pojawia się na poziomie słów. Możesz podzielić słowa na czasowniki, rzeczowniki, przysłówki, przyimki… Możesz pójść dalej i zdefiniować przypadki.
Na poziomie frazy semantyka jest uzupełniona znakami interpunkcyjnymi i logikąkombinacje słów. Na poziomie zdań znajduje się doskonalszy poziom semantyki, a akapit można uznać za kompletną myśl.
Rozwój zorientowany obiektowo z góry określa dziedziczenie właściwości i metod oraz proponuje rozpoczęcie hierarchii obiektów od stworzenia całkowicie abstrakcyjnego przodka. Jednocześnie bez wątpienia analiza każdego potomka będzie miała charakter rekurencyjny i nie będzie się zbytnio różnić na poziomie technicznym w wielu pozycjach (litery, słowa, frazy i zdania). Akapity, podobnie jak całe myśli, mogą wyróżniać się z tej listy, ale nie stanowią one istoty.
Ważne jest, aby przeważającą część algorytmu można było sformułować na poziomie abstrakcyjnego przodka, udoskonalając go na poziomie każdego potomka za pomocą danych i metod wywoływanych z poziomu abstrakcyjnego. W tym kontekście abstrakcja otwiera nowe horyzonty dla rekurencji.
Historyczne cechy OOP
OOP dwukrotnie pojawiło się w świecie oprogramowania, chociaż niektórzy eksperci mogą wskazać pojawienie się chmury obliczeniowej i nowoczesnych pomysłów na obiekty i klasy jako nową rundę w rozwoju technologii IT.
Pojęcia „obiekt” i „obiekt” we współczesnym kontekście OOP są zwykle przypisywane do lat 50. i 60. ubiegłego wieku, ale kojarzą się z 1965 i pojawieniem się Simula, Lisp, Algol, Smalltalk.
W tamtych czasach programowanie nie było szczególnie rozwinięte i nie mogło odpowiednio reagować na rewolucyjne koncepcje. Walka pomysłów i stylów programowania (głównie C/C++ i Pascal) była wciąż odległa, a bazy danych wciąż były koncepcyjnie tworzone.
Pod koniec lat 80. i na początku 90. obiekty pojawiły się w Pascalu i wszyscy pamiętali klasy w C/C++ - to oznaczało nową rundę zainteresowania OOP i to właśnie wtedy narzędzia, głównie języki programowania, przestały być wspierają tylko idee zorientowane obiektowo, ale odpowiednio ewoluują.
Oczywiście, jeśli wcześniej algorytmy rekurencyjne były tylko funkcjami używanymi w ogólnym kodzie programu, teraz rekurencja mogłaby stać się częścią właściwości obiektu (klasy), co zapewniało interesujące możliwości w kontekście dziedziczenia.
Funkcja nowoczesnego OOP
Rozwój OOP początkowo deklarował obiekty (klasy) jako kolekcje danych i właściwości (metody). W rzeczywistości chodziło o dane, które mają składnię i znaczenie. Ale wtedy nie było możliwe przedstawienie OOP jako narzędzia do zarządzania realnymi obiektami.
OOP stało się narzędziem do zarządzania obiektami o „komputerowej naturze”. Skrypt, przycisk, pozycja menu, pasek menu, znacznik w oknie przeglądarki to obiekt. Ale nie maszyna, produkt spożywczy, słowo czy zdanie. Rzeczywiste obiekty pozostały poza programowaniem obiektowym, a narzędzia komputerowe przyjęły nowe wcielenie.
Ze względu na różnice w popularnych językach programowania pojawiło się wiele dialektów OOP. Pod względem semantycznym są one praktycznie równoważne, a ich skupienie na sferze instrumentalnej, a nie użytkowej, pozwala na wyciągnięcie opisu rzeczywistych obiektów pozaalgorytmy i zapewnić ich wieloplatformowe i wielojęzyczne „istnienie”.
Stosy i mechanizmy wywoływania funkcji
Mechanizmy wywoływania funkcji (procedury, algorytmy) wymagają podania danych (parametrów), zwrócenia wyniku oraz zapamiętania adresu operatora, który musi otrzymać sterowanie po zakończeniu funkcji (procedury).
Zazwyczaj do tego celu służy stos, chociaż języki programowania lub sam programista mogą zapewnić różne opcje przekazywania kontroli. Współczesne programowanie przyznaje, że nazwa funkcji może być nie tylko parametrem: może powstać podczas wykonywania algorytmu. Algorytm można również utworzyć podczas wykonywania innego algorytmu.
Koncepcja algorytmów rekurencyjnych, gdy ich nazwy i ciała można określić w momencie tworzenia zadania (wybierając żądany algorytm), rozszerza rekursywność nie tylko na to, jak coś zrobić, ale także kto dokładnie powinien Zrób to. Wybór algorytmu według jego „znaczącej” nazwy jest obiecujący, ale stwarza trudności.
Rekursywność na zestawie funkcji
Nie można powiedzieć, że algorytm jest rekurencyjny, kiedy wywołuje sam siebie i to wszystko. Programowanie nie jest dogmatem, a pojęcie rekursywności nie jest wyłącznym wymogiem wywoływania siebie z ciała własnego algorytmu.
Praktyczne zastosowania nie zawsze dają czyste rozwiązanie. Często trzeba przygotować wstępne dane, a wynik wywołania rekurencyjnego przeanalizować w kontekście całego problemu (całego algorytmu) wogólnie.
W rzeczywistości nie tylko przed wywołaniem funkcji rekurencyjnej, ale także po jej zakończeniu, inny program może lub powinien zostać wywołany. Jeśli nie ma specjalnych problemów z wywołaniem: funkcja rekurencyjna A() wywołuje funkcję B(), która coś robi i wywołuje A(), to od razu pojawia się problem ze zwrotem sterowania. Po zakończeniu wywołania rekurencyjnego funkcja A() musi przejąć kontrolę, aby ponownie wywołać B(), który wywoła ją ponownie. Zwracanie kontroli tak, jak powinno być na stosie z powrotem do B(), jest złym rozwiązaniem.
Programista nie jest ograniczony w wyborze parametrów i może uzupełnić je nazwami funkcji. Innymi słowy, idealnym rozwiązaniem jest przekazanie nazwy B() do A() i pozwolenie, aby sam A() wywoływał B(). W takim przypadku nie będzie problemów ze zwrotem kontroli, a implementacja algorytmu rekurencyjnego będzie bardziej przejrzysta.
Zrozumienie i poziom rekurencji
Problem z tworzeniem algorytmów rekurencyjnych polega na tym, że musisz zrozumieć dynamikę procesu. Przy stosowaniu rekurencji w metodach obiektowych, zwłaszcza na poziomie abstrakcyjnego przodka, pojawia się problem zrozumienia własnego algorytmu w kontekście czasu jego wykonania.
Obecnie nie ma ograniczeń co do poziomu zagnieżdżenia funkcji i pojemności stosu w mechanizmach wywołań, ale jest problem ze zrozumieniem: w którym momencie, który poziom danych lub które miejsce w ogólnym algorytmie zwanym rekursywnym funkcji i na ile dzwoni do siebie.
Istniejące narzędzia do debugowania są często bezsilnepowiedz programiście właściwe rozwiązanie.
Pętle i rekursja
Uważa się, że wykonywanie cykliczne jest równoznaczne z rekurencją. Rzeczywiście, w niektórych przypadkach algorytm rekurencyjny może być zaimplementowany w składni konstrukcji warunkowych i cyklicznych.
Jednakże, jeśli jest jasne, że dana funkcja musi być zaimplementowana za pomocą algorytmu rekurencyjnego, wszelkie zewnętrzne użycie pętli lub instrukcji warunkowych powinno zostać porzucone.
Mam na myśli to, że rozwiązanie rekurencyjne w postaci funkcji korzystającej z siebie będzie kompletnym, funkcjonalnie kompletnym algorytmem. Algorytm ten będzie wymagał od programisty wysiłku, aby go stworzyć, rozumiejąc dynamikę algorytmu, ale będzie to ostateczne rozwiązanie, które nie wymaga zewnętrznej kontroli.
Jakakolwiek kombinacja zewnętrznych operatorów warunkowych i cyklicznych nie pozwoli nam przedstawić algorytmu rekurencyjnego jako pełnej funkcji.
Konsensus rekurencji i OOP
W prawie wszystkich wariantach opracowania algorytmu rekurencyjnego powstaje plan opracowania dwóch algorytmów. Pierwszy algorytm generuje listę przyszłych obiektów (instancji), a drugi algorytm jest w rzeczywistości funkcją rekurencyjną.
Najlepszym rozwiązaniem byłoby zorganizowanie rekurencji jako pojedynczej właściwości (metody), która faktycznie zawiera algorytm rekurencyjny, i umieszczenie całej pracy przygotowawczej w konstruktorze obiektu.
Algorytm rekurencyjny będzie właściwym rozwiązaniem tylko wtedy, gdy zadziałatylko sam, bez zewnętrznej kontroli i zarządzania. Zewnętrzny algorytm może tylko dać sygnał do działania. Efektem tych prac powinno być oczekiwane rozwiązanie, bez wsparcia zewnętrznego.
Rekurencja powinna zawsze być kompletnym, samodzielnym rozwiązaniem.
Intuicyjne zrozumienie i funkcjonalna kompletność
Kiedy programowanie obiektowe stało się de facto standardem, stało się oczywiste, że aby kodować efektywnie, musisz zmienić swoje własne myślenie. Programista musi przejść od składni i semantyki języka do dynamiki semantyki podczas wykonywania algorytmu.
Cecha rekurencji: można ją zastosować do wszystkiego:
- skrobanie sieci;
- operacje wyszukiwania;
- parsowanie informacji tekstowych;
- czytanie lub tworzenie dokumentów MS Word;
- próbkowanie lub analiza tagów…
Charakterystyka OOP: umożliwia opisanie algorytmu rekurencyjnego na poziomie abstrakcyjnego przodka, ale zapewnia odniesienie do unikalnych potomków, z których każdy ma własną paletę danych i właściwości.
Rekurencja jest idealna, ponieważ wymaga funkcjonalnej kompletności swojego algorytmu. Programowanie obiektowe poprawia wydajność algorytmu rekurencyjnego, dając mu dostęp do wszystkich unikalnych elementów podrzędnych.
