Rekurencja: da się ignorować pojedyńczą instrukcję?

0

Mam jakąś funkcję typu void, która ma się rekurencyjnie wykonywać w nieskończoność. Przykładowo:

void recursion()
{
    std::cout << "Ala ma kota\n";

    std::cout << "Ala ma psa\n";
    recursion();
}

Chciałbym aby pierwsza instrukcja tj. std::cout << "Ala ma kota\n"; wykonała się tylko raz (lub N razy). Ale właśnie: jak to ograniczyć, żeby wykonało się tylko raz?

Koniecznie nie chcę przekazywać żadnych dodatkowych parametrów, ani korzystać z zmiennych spoza ciała funkcji. Cała reszta dozwolona.

Z zmienną spoza ciała funkcji można to rozwiązać (niekoniecznie kulturalnie) np. tak:

bool didRecursionStart = false;
void recursion()
{
    if (!didRecursionStart)
        std::cout << "Ala ma kota\n";

    std::cout << "Ala ma psa\n";
    didRecursionStart = true;
    recursion();
}

ale definiując ją w środku ciała funkcji będzie się to nadpisywać i nie zadziała. Próbowałem też robić liczniki, które działałyby na podobnej zasadzie, ale też definicja się jakby nadpisuje.

Jakiś pomysł?

2
Hodor napisał(a):

Koniecznie nie chcę przekazywać żadnych dodatkowych parametrów, ani korzystać z zmiennych spoza ciała funkcji. Cała reszta dozwolona.

Nie ma żadnej reszty – ta informacja nie może być lokalna, więc masz do wyboru albo przekazanie jej w parametrze, albo wydzielenie do globalnej zmiennej.

Mam jakąś funkcję typu void, która ma się rekurencyjnie wykonywać w nieskończoność.

Rekurencja i nieskończoność…?

1

Wydaje mi się, że tak, jak to Opisałeś, to sie nie da. Nurtuja mnie dwie rzeczy: czemu się Bronisz, przed przesyłaniem parametrów? Po co to w ogóle robić, przecież program drukujący coś w nieskończoność, nie jest nawet poprawnym programem.

3

Wydaje mi się, że potrzebujesz zmiennej statycznej w tej funkcji.

Tutaj przykład (co prawda w C ale to bez znaczenia): LINK

0

@Mc_Hammer:

Dzięki, nie znałem tego keywordu static. "Ala ma kota" wykonuje się teraz tylko raz.

void recursion()
{
    static bool didRecursionStart = false;
    if (!didRecursionStart)
        std::cout << "Ala ma kota" << std::endl;

    std::cout << "Ala ma psa" << std::endl;
    didRecursionStart = true;
    recursion();
}
2

Spoko, ale jeśli Twoja rekursja kiedyś by się skończyła (dodałbyś sposób na zakończenie) i chciałbyś ją uruchomić ponownie, to zmienna statyczna wciąż będzie true, więc Ala ma kota nie zostanie wypisane. Musisz przy takim kodzie bardzo uważać, np. żeby przy zakończeniu rekursji, ustawić zmienną statyczną na jej początkową wartość.

Na razie to anty-wzorzec ;)

Napisałem prosty test, jakbyś chciał to sprawdzić nie wywalając apki (przez nieskończoną rekursję):

#include <iostream>

int counter = 0;

void recursion()
{
	static bool didRecursionStart = false;
	if (!didRecursionStart)
		std::cout << "Ala ma kota" << std::endl;

	std::cout << "Ala ma psa" << std::endl;
	didRecursionStart = true;
	counter++;
	if (counter < 10) {
		recursion();
	}
	else {
		counter = 0;
	}
}

int main()
{
    std::cout << "Hello World!\n"; 
	recursion();
	std::cout << std::endl;
	recursion();
}
10

Tak na prawdę, to sposobem który lepiej wyraża intencje (czyli kod ma się wykonać na początku) byłoby zrobienie dwóch funkcji.

void startRecursion() {
    std::cout << "Ala ma kota" << std::endl;
    recursion();
} 

void recursion()
{
    std::cout << "Ala ma psa" << std::endl;
    recursion();
}

Zobaczcie ile niepotrzebnego szumu zniknęło.

Teraz wystarczy wykonać startRecursion().

2

Mom zdaniem najlepszą opcją jest rozłożenie tego na 2 funkcje. Bardziej zastanawia mnie co chcesz zrobić z przepełnieniem stosu. C++ optymalizuje taką rekurencję? Może przechwycisz sygnał sigsegv? :)

2
elwis napisał(a):

Mom zdaniem najlepszą opcją jest rozłożenie tego na 2 funkcje. Bardziej zastanawia mnie co chcesz zrobić z przepełnieniem stosu. C++ optymalizuje taką rekurencję? Może przechwycisz sygnał sigsegv? :)

kompilator pewnie zrobi z tego tail call

1
TomRiddle napisał(a):

Tak na prawdę, to sposobem który lepiej wyraża intencje (czyli kod ma się wykonać na początku) byłoby zrobienie dwóch funkcji.

void startRecursion() {
    std::cout << "Ala ma kota" << std::endl;
    recursion();
} 

void recursion()
{
    std::cout << "Ala ma psa" << std::endl;
    recursion();
}

Zobaczcie ile niepotrzebnego szumu zniknęło.

Teraz wystarczy wykonać startRecursion().

Zgadza się, rozwiązanie chyba najbardziej eleganckie, ale tylko jeśli OP akceptuje brak kontroli nad ilością wykonań.

Hodor napisał(a):

Chciałbym aby pierwsza instrukcja (...) wykonała się tylko raz (lub N razy).

2
Hodor napisał(a):

Mam jakąś funkcję typu void, która ma się rekurencyjnie wykonywać w nieskończoność. Przykładowo:
....
Jakiś pomysł?

Tak, najlepszy pomysł to nie robić tego wcale. Przecież po pewnym czasie przepełni Ci się stos i na tym etapie powinno się skończyć te dywagacje...

5
Mr.YaHooo napisał(a):
Hodor napisał(a):

Mam jakąś funkcję typu void, która ma się rekurencyjnie wykonywać w nieskończoność. Przykładowo:
....
Jakiś pomysł?

Tak, najlepszy pomysł to nie robić tego wcale. Przecież po pewnym czasie przepełni Ci się stos i na tym etapie powinno się skończyć te dywagacje...

Niekoniecznie przepełni.
https://medium.com/software-design/tail-call-optimization-in-c-829b4b257c9a

3

Ciekawe, może ten właściwy algorytm można przekształcić na krótką i czytelną postać iteracyją. ;)

1
vpiotr napisał(a):

Niekoniecznie przepełni.
https://medium.com/software-design/tail-call-optimization-in-c-829b4b257c9a

Owszem. Jednak liczenie na to, ze kompilator zastosuje opcjonalną optymalizację jest powiem delikatnie naiwne. Kod powinien zawierać najmniej niejawnych założeń, a stosowanie nieskończonej rekurencji jest takowym. Można to traktować jako ciekawostkę, ale raczej nigdy nie warto używać takich sztuczek w kodzie produkcyjnym. Najlepiej by było zamienić jak @furious programming problem na postać iteracyjną.

1 użytkowników online, w tym zalogowanych: 0, gości: 1