Quit recursive function when a dynamic condition is met

Question

Using the function from 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);
}

I would like to quit the recursive function and return to the caller function when a certain condition occurs (if it does). So it's like my recursive function is hearing voices that might tell her to quit!

It only happens after str is printed, here:

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

How to do this (stop unfolding the recursion and return to the function caller)?

---

Attempt:

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

just seems to block the execution and never end!

_{PS - I am interested even in c old methodologies.}

Answer 1

A simple solution, given your function currently has no return value, is to use it to indicate whether that terminating condition was met. Then you can use it to immediately exit all recursive calls if the result becomes true.

Not sure if I'm capturing your expected logic correctly here, but the intuitive approach would be something like this:

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 2

The magic function calls itself recursively in two places. So in each of those places, you need to check your exit condition. The answer given by paddy details this.

An alternative for immediate unwinding of the stack is to use setjmp and longjmp which can function as a non-local 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);
    }
}

The setjmp function returns 0 when called directly. When longjmp is called, it is the setjmp function that actually returns, and the return value is the second parameter given to longjmp.

Here, we have a wrapper function which calls setjmp. This sets the jump point for when longjmp is called. Then the recursive function is called. Later, when the recursive function "hears voices" telling it to quit now, it calls longjmp which immediately goes directly to the corresponding setjmp call.

These functions are specified in C99 as well as POSIX, so a POSIX conforming system (i.e. Linux) should still have these available in C89 mode.

If you were to do this in C++, the preferred method would be to throw an exception in the recursive function and catch it in the wrapper function.

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 3

To put it in the simplest form, you could do something like this:

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

Then you initiate the recursion:

bool ret = false;
foo(ret);

In your case you can interupt the recursion by

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

Setting to true will get you out of the entire call tree.

You can do it in C as well, just use a pointer rather than a reference.

Answer 4

This is a non-recursive variant. Basically, it generates all increasing sequences 0 <= a[0] < ... < a[dist-1] < strlen(num), and reverts bits at corresponding indices.

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

Which can be used like this:

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

P.S. Thanks to @ruakh for mentioning a missing optimization in the while - if condition.