rekursive Funktion Beenden, wenn ein dynamischer Zustand

Question

Mit der Funktion von Generate all sequences of bits within Hamming distance t erfüllt ist:

void magic(char* str, int i, int changesLeft) { 
     if (changesLeft == 0) { 
       printf("%s\n", str); 
       return; 
     } 
     if (i < 0) return; 
     // flip current bit 
     str[i] = str[i] == '0' ? '1' : '0'; 
     magic(str, i-1, changesLeft-1); 
     // or don't flip it (flip it again to undo) 
     str[i] = str[i] == '0' ? '1' : '0'; 
     magic(str, i-1, changesLeft); 
} 

Ich möchte die rekursive Funktion beenden und mit dem Anrufer Funktion zurück, wenn eine bestimmte Bedingung auftritt (wenn es der Fall ist). Es ist also meine rekursive Funktion, wenn ich Stimmen höre, die ihr sagen könnten, dass sie aufhören soll!

Es geschieht nur nachstr gedruckt wird, hier:

if (changesLeft == 0) { 
    printf("%s\n", str); 
    int quit_now = voices(str); 
    return; 
} 

Wie dies (stoppen die Rekursion Entfaltung und Rückkehr in die Funktion Anrufer) tun?

---

Versuch:

if (i < 0 || quit_now == 1) return; 

scheint nur die Ausführung und nie enden zu blockieren!

_{PS - Ich bin auch in c alten Methoden interessiert.}

Answer 1

Um es in der einfachsten Form zu setzen, könnten Sie so etwas tun:

void foo(bool & ret) { 
    // doStuff... 
    if (ret) return; 
    foo(ret); 
    // doStuff... 
    if (ret) return; 
    foo(ret); 
} 

Dann initiieren Sie die Rekursion:

bool ret = false; 
foo(ret); 

In Ihrem Fall, dass Sie die Rekursion brechen kann von

if (!changesLeft) { 
    printf("%s\n", str); 
    ret = true; 
    return; 
} 

Wenn Sie den Wert auf "true" setzen, werden Sie aus der gesamten Anrufstruktur entfernt.

Sie können es auch in C tun, verwenden Sie einfach einen Zeiger und nicht eine Referenz.

Answer 2

Eine einfache Lösung, wenn Ihre Funktion derzeit keinen Rückgabewert hat, besteht darin, anzugeben, ob diese Abbruchbedingung erfüllt wurde. Dann können Sie damit alle rekursiven Aufrufe sofort beenden, wenn das Ergebnis wahr wird.

nicht sicher, ob ich Ihre erwartete Logik richtig hier bin erfassen, aber der intuitive Ansatz so etwas wie dieses würde:

int magic(char* str, int i, int changesLeft) { 
    int result; 
    if (changesLeft == 0) { 
      printf("%s\n", str); 
      return voices(str); 
    } 
    if (i < 0) return 0; 

    // flip current bit 
    str[i] = str[i] == '0' ? '1' : '0'; 
    result = magic(str, i-1, changesLeft-1); 

    if(!result) { 
     // or don't flip it (flip it again to undo) 
     str[i] = str[i] == '0' ? '1' : '0'; 
     result = magic(str, i-1, changesLeft); 
    } 

    return result; 
} 

Answer 3

Die magic Funktion ruft sich selbst rekursiv an zwei Stellen. Also müssen Sie an jedem dieser Orte Ihren Ausgangszustand überprüfen. Die Antwort von Paddy sagt dies aus.

Eine Alternative zum sofortigen Abwickeln des Stapels ist die Verwendung von setjmp und longjmp, die als nicht lokale goto fungieren können.

jmp_buf magic_buf; 

void magic_int(char* str, int i, int changesLeft) { 
     if (changesLeft == 0) { 
       printf("%s\n", str); 
       if (voices(str)) { 
        longjmp(magic_buf, 1); 
       } 
       return; 
     } 
     if (i < 0) return; 
     // flip current bit 
     str[i] = str[i] == '0' ? '1' : '0'; 
     magic_int(str, i-1, changesLeft-1); 
     // or don't flip it (flip it again to undo) 
     str[i] = str[i] == '0' ? '1' : '0'; 
     magic_int(str, i-1, changesLeft); 
} 

void magic(char* str, int i, int changesLeft) { 
    if (!setjmp(magic_buf)) { 
     magic(str, i, changesLeft); 
    } 
} 

Die setjmp Funktion gibt 0 wenn direkt aufgerufen. Wenn longjmp aufgerufen wird, ist es die setjmp Funktion, die tatsächlich zurückgibt, und der Rückgabewert ist der zweite Parameter, der an longjmp übergeben wird.

Hier haben wir eine Wrapper-Funktion, die setjmp aufruft. Damit wird der Sprungpunkt für den Zeitpunkt longjmp festgelegt. Dann wird die rekursive Funktion aufgerufen. Später, wenn die rekursive Funktion "hört Stimmen" sagt es jetzt zu beenden, ruft es longjmp, die sofort direkt auf die entsprechende setjmp Aufruf geht.

Diese Funktionen sind sowohl in C99 als auch in POSIX angegeben, daher sollte ein POSIX-konformes System (d. H. Linux) diese im C89-Modus noch verfügbar haben.

Wenn Sie dies in C++ tun würden, wäre die bevorzugte Methode, eine Ausnahme in die rekursive Funktion zu werfen und sie in der Wrapper-Funktion abzufangen.

struct magic_voices { 
    int rval; 
}; 

void magic_int(char* str, int i, int changesLeft) { 
     if (changesLeft == 0) { 
       printf("%s\n", str); 
       int rval = voices(str); 
       if (rval) { 
        struct magic_voices ex; 
        ex.rval = rval; 
        throw ex; 
       } 
       return; 
     } 
     if (i < 0) return; 
     // flip current bit 
     str[i] = str[i] == '0' ? '1' : '0'; 
     magic_int(str, i-1, changesLeft-1); 
     // or don't flip it (flip it again to undo) 
     str[i] = str[i] == '0' ? '1' : '0'; 
     magic_int(str, i-1, changesLeft); 
} 

void magic(char* str, int i, int changesLeft) { 
    try { 
     magic(str, i, changesLeft); 
    } catch (struct magic_voices ex) { 
     printf("rval=%d\n", ex.rval); 
    } 
} 

Answer 4

Dies ist eine nicht-rekursive Variante. Im Grunde erzeugt es alle ansteigenden Sequenzen 0 <= a[0] < ... < a[dist-1] < strlen(num) und setzt Bits bei entsprechenden Indizes zurück.

void print(const char* num, const vector<int>& a) { 
    size_t k = 0, n = strlen(num); 
    for (size_t i = 0; i < n; ++i) 
     if (k < a.size() && a[k] == i) { 
      cout << (num[i] == '0') ? '1' : '0'; 
      ++k; 
     } 
     else 
      cout << num[i]; 
    cout << endl; 
} 

void hamming(const char* num, size_t dist) { 
    assert(dist > 0); 
    vector<int> a(dist); 
    size_t k = 0, n = strlen(num); 
    a[k] = -1; 
    while (true) 
     if (++a[k] > n - dist + k) 
      if (k == 0) 
       return; 
      else { 
       --k; 
       continue; 
      } 
     else 
      if (k == dist - 1) { 
       print(num, a); 
       // conditional return here 
      } 
      else { 
       a[k+1] = a[k]; 
       ++k; 
      } 
} 

, die wie folgt verwendet werden kann:

int main() 
{ 
    hamming("0000", 2); 
    /* output: 
     1100 
     1010 
     1001 
     0110 
     0101 
     0011 
    */ 
} 

P. S. Danke an @ruakh für die Erwähnung einer fehlenden Optimierung im while - if Zustand.