Hello !

I have a task that is difficult for me to handle. The task is: Create recursive function that can be generate a string of length N (N <= 100), formed by the letters 'A', 'B' and 'C' and does not containing two identical adjacent substring. For example: enter for N = 6 and the program should generate such a string in which no one else to repeated substrings: ABACAB. Wrong strings are: AABACA - because 'A' is to 'A'; ABCBCA - as 'BC' is to 'BC' and ABCABC is also wrong because 'ABC' is to 'ABC'.

I made a version of the program but an iterative way, here is the code:

#include <iostream>
#include <ctime>

using namespace std;

const char letters[] = "ABC";

char generate_rand()
{

    return letters[rand() % 3];

}

int check(char *s, int pos) 
{

    for (int i = 1; i <= (pos + 1)/2; i++) 
    {

        int flag = 1;

        for (int j = 0; j < i; j++)

        if (s[pos-j] != s[pos-i-j]) 
        {

            flag = 0; 
                break;

        }

        if (flag)
            return 1;

    }
    return 0;
}

int main() 
{
    char s[100];
    int n;

    cout << "enter n: ";
    cin >> n;

    srand(time(NULL));

    for (int i = 0; i < n; i++) 
    {

        do
        {

            s[i] = generate_rand();

        } while (check(s, i));

        cout << s[i] << " ";

    }

    cout << " ok" << endl;

    system("pause");
    return 0;
}

I think the entrance of the recursive function may need to be the number of characters in the string, which will seek to repeat with an adjacent string and each time increased by 1, but not more than half the length of the original string, but do not know how to do it.

Yes, i know. I did iterative version and now I have to do recursive, but do not know how

This question has already been answered. Start a new discussion instead.