gsamaras gsamaras - 10 days ago 7
C Question

Quit recursive function when a dynamic condition is met

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 old methodologies.

Answer

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