Бросить рекурсивную функцию, когда динамическое условие выполняется

Question

Использование функции от Generate all sequences of bits within Hamming distance t:

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); 
} 

Я хотел бы выйти из рекурсивной функции и вернуться к функции вызывающего абонента, когда возникает определенное условие (если он делает). Так что, как и моя рекурсивная функция, слышу голоса, которые могут сказать ей уйти!

Это происходит только после того, как str печатается здесь:

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

Как это сделать (остановить разворачивание рекурсию и вернуться к функции вызывающей)?

---

Попытка:

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

только кажется, чтобы блокировать выполнение и никогда не закончится!

_{PS - Меня интересует даже в c старые методологии.}

Answer 1

Выражаясь в простейшей форме, вы могли бы сделать что-то вроде этого:

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

Затем вы начинаете рекурсию:

bool ret = false; 
foo(ret); 

В вашем случае вы можете ПРЕРЫВАЙТЕ рекурсию на

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

Установка в true приведет к выходу из всего дерева вызовов.

Вы также можете сделать это на C, просто используйте указатель, а не ссылку.

Answer 2

Простое решение, учитывая, что ваша функция в настоящее время не имеет возвращаемого значения, заключается в использовании его для указания того, было ли выполнено это условие завершения. Затем вы можете использовать его для немедленного выхода из всех рекурсивных вызовов, если результат станет истинным.

Не уверен, что если я захватывая планируемую логику правильно здесь, но интуитивный подход будет что-то вроде этого:

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

magic функция вызывает себя рекурсивно в двух местах. Поэтому в каждом из этих мест вам нужно проверить свое условие выхода. Ответ, который дает падди, подробно описывает это.

Альтернативой немедленного разматывания стека является использование setjmp и longjmp, который может функционировать как нелокальный goto.

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); 
    } 
} 

setjmp функция возвращает 0, когда вызывается непосредственно. Когда вызывается longjmp, это фактически возвращается функция setjmp, а возвращаемое значение является вторым параметром, заданным longjmp.

Здесь у нас есть функция обертки, которая вызывает setjmp. Это устанавливает точку перехода, когда вызывается longjmp. Тогда вызывается рекурсивная функция. Позже, когда рекурсивная функция «слышит голоса», говоря ей, чтобы выйти сейчас, она вызывает longjmp, которая сразу же переходит непосредственно к соответствующему вызову setjmp.

Эти функции указаны на C99, а также в POSIX, поэтому система, соответствующая POSIX (то есть Linux), должна по-прежнему иметь доступную в режиме C89.

Если вы должны были сделать это на C++, предпочтительным методом было бы выбросить исключение в рекурсивную функцию и уловить его в функции обертки.

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

Это нерекурсивный вариант. В основном, он генерирует все возрастающие последовательности 0 <= a[0] < ... < a[dist-1] < strlen(num) и возвращает биты с соответствующими индексами.

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; 
      } 
} 

который может быть использован, как это:

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

P.S. Благодаря @ruakh для упоминания недостающей оптимизации в состоянии while - if.