Zapisać funkcję rekurencyjną w sposób iteracyjny Mariusz: https://ideone.com/iwmeYG Iteracyjne wstawianie wziąłem z książki CLRS wprowadzenie do algorytmów Rekurencyjną funkcję przekształcającą drzewo w listę dwukierunkową napisałem na podstawie procedury przechodzącej drzewo in order także wziętej z książki CLRS wprowadzenie do algorytmów W rekurencyjnej procedurze przechodzącej drzewo podmieniłem wypisywanie danych na wstawianie węzła na ogon listy Jak zapisać procedurę rekurencyjną w postaci iteracyjnej ? Z tego co widzę to jedno wywołanie jest ogonowe ale oprócz niego jest jeszcze jedno wywołanie

Pytający: https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

Mariusz: template<class T> void DoublyLinkedList<T>::BSTtoDLL(Link<T> *root,DoublyLinkedList<T> &L) { while(root != NULL) { BSTtoDLL(root−>getPrevious(),L); if(L.isEmpty()) L.setFirst(root); else L.getLast()−>setNext(root); root−>setPrevious(L.getLast()); L.setLast(root); root = root−>getNext() } } Jak zamienić wywołanie ogonowe na pętlę kiedyś pokazał Trivial ale co jeśli oprócz wywołania ogonowego są jeszcze inne wywołania rekurencyjne ?

Mariusz: Nie jestem pewien czy ich rozwiązanie będzie równoważne z wersją rekurencyjną

Pytający: Oni są pewni. https://ideone.com/PuqaKw

Mariusz: Wiem że działa bo sprawdzałem ale nie jestem pewny czy działa tak samo jak wersja rekurencyjna poza tym bardziej mi chodzi nie tyle o tę konkretną funkcję tylko o zapisywanie procedur rekurencyjnych w sposób iteracyjny a ty nie pomagasz odsyłaniem do takich stronek

Mariusz: Weźmy sortowanie przez scalanie // wersja rekurencyjna void MergeSortR(int *A,int l,int r) { int m; if(l < r) { m = (l+r)/2; MergeSortR(A,l,m); MergeSortR(A,m+1,r); Merge(A,l,m,r); } } //wersja iteracyjna void MergeSortI(int *A,int n) { int curr,left,mid,right; curr = 1; while(curr <= n) { left = 1; while(left+curr <= n) { mid = left + curr − 1; if(left +2*curr − 1 < n) right = left +2*curr − 1; else right = n; Merge(A,left,mid,right); left += 2*curr; } curr *= 2; } } Obydwie procedury działają dla tablicy A[1..n] ale czy działają w ten sam sposób ?

Pytający: Tylko co znaczy "działa tak samo"? Dla mnie jest to oczywiste, że działa inaczej (aż tak kompilatory nie cudują w kodzie). Jak działa rekurencja? Jak kompilatory radzą sobie z wywołaniami rekurencyjnymi? Dlatego wystarczy stos i nie widzę sensu w dalszym rozwodzeniu się nad tym tematem (no chyba że zajmujesz się optymalizacją kompilatora lub czymś podobnym... ja się tym nie zajmuję). Cóż, pozostaje mi po raz kolejny Cię pozdrowić i życzyć Ci powodzenia w poszukiwaniu bardziej pomocnych osób ode mnie. Ja nic konstruktywnego tu nie wniosę. Serdecznie pozdrawiam.

Mariusz: Jeszcze może jedno związane z rekurencją i programowaniem obiektowym https://pastebin.com/wqgDLLaH Tutaj wstawianie napisane rekurencyjnie powoduje błąd Na liście / drzewie napisanym strukturalnie nie powoduje jednak tego błędu ? "Cóż, pozostaje mi po raz kolejny Cię pozdrowić i życzyć Ci powodzenia w poszukiwaniu bardziej pomocnych osób ode mnie. Ja nic konstruktywnego tu nie wniosę. Serdecznie pozdrawiam" Jeżeli twoja pomoc ma się ograniczać do wyszukiwania tematów w google to strata niewielka Jak działa rekurencja? Jak kompilatory radzą sobie z wywołaniami rekurencyjnymi? Dobre pytania jednak nie odpowiedziałeś na nie a rozwiązanie które wyszukałeś po pierwsze nie jest twoje a po wtóre ja już wcześniej je znalazłem "Tylko co znaczy "działa tak samo"? Dla mnie jest to oczywiste, że działa inaczej (aż tak kompilatory nie cudują w kodzie)." Działa inaczej nie dlatego że "aż tak kompilatory nie cudują w kodzie" tylko zastosowano inne podejście − pominięto etap dzielenia Do tej pory to raczej ty "cudujesz" zamiast sensownie odpowiadać

Pytający: "Tutaj wstawianie napisane rekurencyjnie powoduje błąd Na liście / drzewie napisanym strukturalnie nie powoduje jednak tego błędu ?" Powielasz błąd, który już Ci kilkukrotnie wskazywałem − posługujesz się adresami zmiennych lokalnych/tymczasowych (gdzieś na stosie), nie zaś tymi wskazującymi na pamięć zaalokowaną na stercie. Resztę szkoda komentować.

Mariusz: To jak odwołać się do tej pamięci na stercie Dla funkcji template<class T> void DoublyLinkedList<T>::BSTinsert(Link<T> **root,Link<T> *x) otrzymałem następujący komunikat o błędzie F:\Work_Cpp\ideone_nubXls.cpp|302|error: lvalue required as unary '&' operand| Dla funkcji template<class T> void DoublyLinkedList<T>::BSTinsert(Link<T> *&root,Link<T> *x) otrzymałem następujący komunikat o błędzie F:\Work_Cpp\ideone_nubXls.cpp|302|error: invalid initialization of non−const reference of type 'Link<int>*&' from an rvalue of type 'Link<int>*'| Jak poprawie przekazywać parametry przez referencję w funkcji rekurencyjnej ?

Pytający: Tak samo jak w funkcji nierekurencyjnej... Toć komunikaty są konkretne, czegóż w nich nie rozumiesz?

Mariusz: Co do tej funkcji rekurencyjnej to wolałbym abyś pokazał sposób pozbywania się rekurencji krok po kroku , np z wykorzystaniem tego że jedno z wywołań jest ogonowe zamiast wyszukiwania cudzych rozwiązań i wklejania do nich odnośników i to bez żadnego komentarza Wątpię czy gdybym miał podobną funkcję to czy umiałbym przepisać ją na funkcję iteracyjną Gdybyśmy mieli zamienić rekurencyjną funkcję realizującej przechodzenie preorder na jej postać iteracyjną to jak byś napisał wersję iteracyjną (Ja już napisałem iteracyjną wersję ale chciałbym poznać twoją propozycję twoją a nie wyszukaną gdzieś w sieci) Co do tego błędu to też nie zaproponowałeś

Mariusz: Co do tego błędu to też nie zaproponowałeś sposobu jego naprawienia

Pytający: Skoro bawi Cię sprawdzanie mnie: void preorderRecursive(node* ptr) { if(!ptr) return; doSomeAction(ptr−>data); preorderRecursive(ptr−>left); preorderRecursive(ptr−>right); } void preorderIterative(node* ptr) { if(!ptr) return; std::stack<node*> s; s.push(ptr); while(!s.empty()) { ptr = s.top(); s.pop(); doSomeAction(ptr−>data); if(ptr−>right) s.push(ptr−>right); if(ptr−>left) s.push(ptr−>left); } } Komentarzy brak, bo i tak je olewasz. Pozbądź się tych zbędnych getterów/setterów, a i owe błędy magicznie znikną... komunikatów kompilatora Ci tłumaczyć nie będę.

Pytający: Ale masz kolejny link zagadkę: https://ideone.com/TKWton .

Mariusz: No właśnie nie wykorzystałeś wywołania ogonowego Na stos można było odkładać jeden węzeł Odkładanie drugiego węzła można było zastąpić przejściem do lewego węzła a instrukcje występujące po zdjęciu węzła ze stosu wziąć w pętle Jeśli chodzi o preorder to ciekaw jestem czy zauważyłeś że quick sort ma podobnie wyglądającą funkcję rekurencyjną W przechodzeniu inorder też występuje wywołanie ogonowe i ciekaw byłem jak to wykorzystać Co do zagadki to czy podobna sytuacja wystąpiła w kodzie który podesłałem bo komunikat o błędzie jest ten sam W funkcji którą podajesz jako argument dla funkcji przekazującej argument przez referencję zwracasz jakąś stałą wartość A jakaś inna propozycja poprawienia tego błędu Zbyt dużo funkcji korzysta z tych getterów i setterów

Pytający: "No właśnie nie wykorzystałeś wywołania ogonowego Na stos można było odkładać jeden węzeł Odkładanie drugiego węzła można było zastąpić przejściem do lewego węzła a instrukcje występujące po zdjęciu węzła ze stosu wziąć w pętle" No nie wykorzystałem. No można było. Ale chciałeś iteracyjną wersję i taką dostałeś, długo się nad nią nie zastanawiałem. Bym chciał lepszej wersji, to bym takowej poszukał − nie sprawia mi przyjemności wymyślanie czegoś, co i tak dawno zostało wymyślone... "Jeśli chodzi o preorder to ciekaw jestem czy zauważyłeś że quick sort ma podobnie wyglądającą funkcję rekurencyjną" Oczywiście, że nie zauważyłem. Quick sorta widuję chyba tylko w Twoich postach. Gdy chcę coś posortować, korzystam z gotowej funkcji. "A jakaś inna propozycja poprawienia tego błędu Zbyt dużo funkcji korzysta z tych getterów i setterów" Zamień zwracany typ dla getPrevious() i getNext() z Link<T>* na Link<T>*&. Oczywiście zupełnie psuje to enkapsulację, ale jak już wcześniej Ci pisałem, węzeł listy sam w sobie nie powinien być udostępniony użytkownikowi, to tylko szczegół implementacyjny. Tu masz Twój kod z tutejszego pierwszego postu pozbawiony getterów, setterów i z Link jako klasą zagnieżdżoną (wyrzuciłem też funkcje do wypisywania węzła jako zbędne): https://ideone.com/QGlHQQ I zamiana nie zajęła więcej jak 15 minut, tyle roboty.

Mariusz: " nie sprawia mi przyjemności wymyślanie czegoś, co i tak dawno zostało wymyślone..." no i między innymi dlatego nie nadajesz się na nauczyciela Dodatkowo nie wytłumaczyłeś żadnego tematu tak od początku Jako przykład przypomnę pewne zadanie Kiedyś na innym forum dałem jako zadanie zaproponować algorytm sortujący linie w pliku i jeden próbował mi go opisać I całkiem nieźle mu to wyszło, napisał nawet pseudokod procedury scalającej Wprowadziłem drobne poprawki do jego pseudokodu i na podstawie algorytmu który opisał napisałem iteracyjne sortowanie list przez scalanie Dałem ten kod tutaj bo chciałem zaoszczędzić na jednym scalaniu przez co posortowana lista nie znalazła się w this tylko w jakiejś zmiennej i jeśli dobrze pamiętam wystąpił problem z destruktorem Koleś na tamtym forum dość dobrze mi opisał ten algorytm prawdopodobnie dlatego że sam kiedyś napisał program wykorzystujący podobny algorytm Ty byś tego algorytmu mi nie opisal Kiedyś dałem do rozwiązania zadanie aby zmodyfikować ten algorytm tak aby scalać serie na przemian do dwóch list Wtedy można by było funkcję rozdzielającą wywołać tylko raz Jeśli dobrze pamiętam nie udało ci się wtedy wyszukać cudzego rozwiązania Nie podpowiedziałeś także jak zmodyfikować tę procedurę Jeśli chodzi o wyżej wspomniany algorytm to tutaj podpowiedziałeś mi że tutaj może chodzić o domyślny destruktor ale jestem pewien że nie opisałbyś mi tego algorytmu od początku Jako tako odpowiadałeś w temacie o otoczce wypukłej Twoja funkcja porównująca i inne podpowiedzi pozwoliły mi napisać algorytm działający na tablicy Może nie od razu ale później po zastanowieniu domyśliłem się że znowu wyszukałeś i skopiowałeś cudze rozwiązanie Kiedyś od razu poznałem że dzieciak Metis nie umie programować ale mimo to pisał jakieś bzdury nic nie wnoszące do tematu i później okazało się że miałem rację Twoje wpisy też niewiele wnoszą do tematu ale w twoim przypadku z twierdzeniem że nie umiesz programować byłbym ostrożny

Mila: Mariuszu, jesteś niegrzeczny.

Pytający: Mariuszu, to, co piszesz, nie jest już nawet śmiechu warte. Pozdrawiam i żegnam ostatecznie, boś jednak niereformowalny (i nie ma sensu zaśmiecać tego forum takimi "dyskusjami"). Pomyślności.

Mariusz: Gdybyś odpowiadał przynajmniej tak jak w temacie o otoczce to byłoby w porządku Ja też doszedłem do wniosku że twoje wpisy w wątkach założonych przeze mnie poza tymi związanymi z otoczką i może jedną odpowiedzią dotyczącą programowania obiektowego zaśmiecają forum Mila czemu uważasz że jestem niegrzeczny ? Uważasz że wpisy zacznij od początku albo kopiowanie cudzych rozwiązań bez żadnego komentarza wnoszą coś do tematu Poza tym gdy kiedyś koleś próbował mi wytłumaczyć temat i całkiem nieźle mu to wychodziło jak na użytkownika forum który prawdopodobnie nie miał nic do czynienia z dydaktyką tylko kiedyś podobny program napisał to go pochwaliłem Jak przejrzysz tematy jakie założyłem to tutaj to jedynie w temacie o otoczce Pytający jako tako odpowiadał Może ci się wydawać że jestem niegrzeczny ale po prostu nie lubię wpisów które niewiele wnoszą do tematu

jc: Mariusz, powtórzę, jesteś niegrzeczny.