2

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.

Improve this question
10
  • Did you try goto: instead of return? Commented Nov 28, 2016 at 0:20
  • @hbagdi the black sheep? :O I have never touched it, but if you post an answer that proves it can come in handy, I would be willing to....I am over 21 now!!! =) // didn't get that was trolling :/ Commented Nov 28, 2016 at 0:21
  • 1
    Don't. They are trolling you. Commented Nov 28, 2016 at 0:22
  • Alternatively you could just consider a non-recursive implementation. Commented Nov 28, 2016 at 0:38
  • @AlexD if I had one, of course! Maybe I should try to write one (or if you have one already, feel free to post it as an answer)! :) Commented Nov 28, 2016 at 0:39

4 Answers 4

Reset to default
3

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; }
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

And result should get its value right after printf("%s\n", str);, as I would like to, right?
Yes, in each caller, because you return 1 after that printf. And every caller up the stack stops making recursive calls when they get a non-zero result. They all return that result to pass it all the way back up. Another bonus is that the first caller will know whether the operation met its terminating condition or not. And so the function itself doesn't have to have the printf. You could say: if( magic(str, 0, x) ) printf( "OK: %s\n", str ); else printf( "No answer\n" );
Oh, sorry, I only just noticed I hadn't handled the voices thing. Copy/paste and lazy reading.... I've updated.
1

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.

Improve this answer

3 Comments

This is actually similar to how I do "exception handling" in C - granted it is arduous, but if you want clean and proper stack unwinding that's the way to go. longjmp will whoosh past all the stuff that needs to happen along the stack frames, and you're gonna have a bad time. It is only acceptable if you don't have anything to handle - no deallcations, no de-initializations and so on.
Beware there can be memory ordering issues and race conditions accessing the true value of ret between threads, and a proper solution may involve the use of an atomic.
@paddy this really doesn't look like a multi-threaded scenario. And race condition protection in multi-threaded scenarios goes without saying.
1

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); } }
Improve this answer

7 Comments

Are these babies standard C/C++?
C and C++ are two different languages. Use of explicit jumps in C++ is highly discouraged. Especially for something as simple as ordinary termination of a recursion. The compiler is free to decide on a jump if it wants to optimize the return. The programmer should not be concerned with that detail under ordinary circumstances.
I think this is a useful answer, which provides insight into more of a systems-level approach. It's good to know these things are there, but to exercise discretion about using them.
@paddy Added a C++ solution involving exceptions.
I think your solution will suffer from the same problem as paddy's, please see my update.
|
1

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.

Improve this answer

4 Comments

Alex, sorry for commenting after so much time, but wouldn't that cout << (num[i] == '0') ? '1' : '0'; be more naturally written as cout << (num[i] == '0') ? '0' : '1';, or it should be the way you wrote it? Oh, it has to be the way you wrote it, but why? =)
@gsamaras The vector a is supposed to keep indices for which bits have to be inverted. So if a contains the current index i, we print 1 instead of 0 and vice versa. Otherwise we print the bit as is (see else-part).
Thank you AlexD, I am very intrigued by the algorithm and trying to analyze its Time Complexity, as shown here.
@gsamaras Oh, sorry, if I'd know it is intended for O-complexity, I would be more accurate and remove dry run, as ruakh suggested! I added a comment to Paul's answer.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.