How do I break out of a recursion in C?

16.5k views Asked by At

I'm still a newbie in programming, so please tolerate my poor syntax and logic if any were bad. I've been writing a cryptarithmetic puzzle solver in C. It reads 3 words from the user, calculates their value and prints them to screen. (e.g send+more=money -> 9567+1085=10652)

I tried something similar to permutation algorithm. It can do the calculations but for some inputs, results are printed multiple times:

Example output

How can I modify my code so the first time the printf commands under if (n1+n2==n3) are processed recursion ends and the program returns to the main function?

/* Swaps the two elements of an array. */
void swap(int v[], int i, int j) {
    int t;
    t = v[i];
    v[i] = v[j];
    v[j] = t;
}

/* Solves the Cryptarithmetic puzzle. */
int solve(int v[], int n, int i, char s1[], char s2[], char s3[], char letters[]) {
    int k, m, j, t = 0, power, n1 = 0, n2 = 0, n3 = 0;
    if (i == n) {
        /*....some codes that 
         * calculate the value of each input word.....*/

        /*This part verifies the values and if they are correct, prints them to screen*/
        if (n1 + n2 == n3) {
            printf("found!\n");
            printf("\n%s :  %6d\n", s1, n1);
            printf("%s :  %6d\n", s2, n2);
            printf("%s :  %6d\n", s3, n3);
        }
    } else
        for (j = i; j < n; j++) {
            swap(v, i, j);
            solve(v, n, i + 1, s1, s2, s3, letters);
            swap(v, i, j);
        }
}
2

There are 2 answers

0
JS1 On BEST ANSWER

Three changes are needed. First, you need to return something once you solved it:

    printf ("%s : %6d\n", s3 , n3);
    return 1;

Next, you need to check the return value when you recurse, and stop if you found a solution:

    if (solve (v, n, i+1,s1,s2,s3,letters))
        return 1;

Last, if you don't find a solution, you need to return 0:

    }
    return 0;
}
2
lion On

You could use setjmp()/longjmp(). For this you need to:

#include <setjmp.h>

then a global variable:

jmp_buf env;

Then in main (or wherever you call your recursive function) you do:

if(!setjmp(env)) recursiveSolve();

and then when you find the solution:

if(solutionFound) longjmp(env, 1);

and it will return to main like nothing happened - but your solution found.