Jestem blisko stylu programowania, o którym już dawno myślałem. Chcę ominąć ograniczenia, które przyjmuje się za podstawy programowania rekursywnego.
Tymi ograniczeniami są: szybkie zużycie stosu na ciała wywołań kolejnych funkcji, wielokrotne obliczane tego samego.
Moje podejście wydaje się omijać oba ograniczenia. Zamiast stosu używam kolejki, dzięki czemu nie muszę pamiętać wcześniejszego wywołania, oraz ograniczam pętle, wskazując konkretnie, gdzie odkładać wyniki pośrednie.
Wiążą się z tym jednak inne problemy do rozwiązania. Pierwszym z nich jest: gdzie pojawią się wyniki? Należy w ciele wywołania funkcji trzymać adres klasy, do której trafią wyniki. Ma też inne zachowania, np. pozwala zastosować funkcje wielowartościowe.
Zastosowałem ten sposób do znajdywania wzorca w napisie. Najlepsze logarytmy mają złożoność O(n+m), gdzie n jest długością napisu, a m długością wzorca. Ta złożoność u mnie zachodzi dla dokładnie jednego wzorca, kiedy nie ma tekstów zaczynających się tak samo jak wzorzec. Moją złożoność szacuję na O(n*m), zależy od napisu i wzorca. Trzeba dodatkowo zapamiętać położenie pierwszej zgodności wartości oraz położenie wyników, te dane przy wychodzeniu z funkcji (rekursywnych mojego typu) są tracone.
Wywołanie odbywa się przez zapakowanie do klasy i uruchomienie ciągu:
0. [szukajTekstu, napis, indeksNapisu, wzorzec, indeksWzorca, skadZgodnosc, wynik]
Klasa ma jedną metodę, która porównuje ze sobą dwie wartości
napis[ indeksNapisu ] == wzorzec[ indeksWzorca ]
Jeżeli są zgodne oraz skadZgodnosc jest ustawiona na jakąś pozycję, kolejny znak tekstu jest zgodny ze wzorcem. Jeśli nie, ustawia się skadZgodnosc na pozycję indeksNapisu, oraz wywołuje dwie funkcje, przez odłożenie ciągów
1. [szukajTekstu, napis, indeksNapisu+1, wzorzec, indeksWzorca+1, skadZgodnosc, wynik]
dla kontynuacji, oraz
2. [szukajTekstu, napis, indeksNapisu+1, wzorzec, 0, nil, wynik]
dla poszukiwania początku kolejnego wzorca w napisie.
Jeśli wartości nie są zgodne, rekursja jest zatrzymywana dla tego konkretnego przypadku, ale póki nie sprawdzony jest cały napis, należy ponownie wywoływać 2.
Oczywiście przy wywołaniu rekursywnym należy zacząć od przypadków szczególnych, indeksNapisu maksymalny to zakończenie tego ciągu rekursji, zaś indeksWzorca maksymalny to odłożenie do wyniku ciągu
3. [wynik, ?, skadZgodnosc]
W miejsce pytajnika należy podać informację o przebiegu. Nie wiadomo, czy algorytm się zatrzyma i kiedy. Dlatego klasa wynik musi być czymś w rodzaju sprytnego wskaźnika dla wywołań.
Jedno przejście po napisie wystarczy, by wyłapać wszystkie wystąpienia wzorca. Szukając 'na' w tekście 'ananas nasz' algorytm zwrócił tablicę [1,3,7]. Ale dla tego samego wzorca i napisu 'nanas nasz' o wyniku [0,2,6] pojawił się problem, jak trzymać w pamięci skadZgodnosc. Należało go zwiększyć o 1, gdyż inaczej blokowało wynik. Przyczyna nieznana, wszystkie dane były traktowane praktycznie jako void i kompilator nie wiedział co zrobić z semaforem na nil. Ewentualnie można przyjąć liczenie pozycji od 1, zaś 0 stosować jako semafor.
