Having trouble with recursion

Question

I am trying to make a program which prints all the possible permutations of the string "A?B?AB?" via replacing question marks with A or B. I can't understand why my code works the way it does and need help improving it.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* rec(char s[8]){
    int i=0;
    for(;i<strlen(s);i++){
    if(s[i]=='?'){
        s[i]='A';
        rec(s);
        s[i]='B';
        rec(s);
        s[i]='?';
    }
    }
    for(int k=0;k<strlen(s);k++){
        if(s[k]=='?')
            i=-1;
    }
        if(i!=-1)
            printf("%s\n",s);

    return s;
}

int main(){
    char s[8]="A?B?AB?";
    rec(s);
}

Perhaps you should take some time to learn how to use a *debugger* to be able to step through the code statement by statement while monitoring variables and their values. — Some programmer dude, May 03 '21 at 19:56
You probably want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) You may also want to read this: [How to debug small programs?](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). — Andreas Wenzel, May 03 '21 at 19:58
Do you have a specific problem or a question in mind? Or do you need help understanding recursion in general? Please take look at the [tour](https://stackoverflow.com/tour) for what you need to include in your question. It will help us to help you better. — RisingSun, May 03 '21 at 20:37

score 0 · Answer 1 · answered May 03 '21 at 20:49

You only need to look at one character at a time. Try this:

#include <stdio.h>

void PrintPermutationsFrom(int i, char s[])
{
    if (s[i] == '?') {
        s[i] = 'A';
        PrintPermutationsFrom(i + 1, s);
        s[i] = 'B';
        PrintPermutationsFrom(i + 1, s);
        s[i] = '?';
    } else if (s[i] != '\0') {
        PrintPermutationsFrom(i + 1, s);
    } else {
        puts(s);
    }
}


void PrintPermutations(char s[])
{
    PrintPermutationsFrom(0, s);
}


int main(void)
{
    char s[] = "A?B?AB?";

    PrintPermutations(s);
    return 0;
}

score 0 · Accepted Answer · answered May 03 '21 at 21:01

This should do the trick:

#include <stdio.h>
#include <string.h>

void rec(char *str, int size, int depth){
    for (int i = depth; i < size; i++){
        if (str[i] == '?'){
            str[i] = 'A';
            rec(str, size, i + 1);

            str[i] = 'B';
            rec(str, size, i + 1);

            str[i] = '?';
            return;
        }
    }

    printf("%s\n", str);
}

int main(){
    char s[8] = "A?B?AB?";
    rec(s, strlen(s), 0);
}

It's much like August's solution, but I did decide to do some looping until it found the next question mark. That should avoid having too big of a callstack, which could lead to stack overflow, with really big strings. (Note: I didn't test it, so there could still be some minor problems)

score -1 · Answer 3 · answered May 03 '21 at 20:26

I can't understand why my code works the way it does and need help improving it.

The rec code does simply too much in that after having replaced a ? with both A and B and called itself, it continues iterating over s and generates further output. That is too much because after the first found ?, the recursive invocations already have handled all following ? and generated all arrangements. To correct this, just insert a break; after s[i]='?';.

Having trouble with recursion

3 Answers3