Выделение памяти для рекурсивной функции strcat() в C

Учитывая контекст другого вопроса, я думаю, вам следует организовать первоначальный вызов функций, чтобы он задавал начало и конец массива, скажем, из 100 символов. По мере того, как вы работаете рекурсивно, вы увеличиваете начальный указатель, который вы передаете другим функциям соответствующим образом.

Этот код работает для меня:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* One of these is sufficient; symmetry requires both */
static char *print_S(char *dst, char *end);
static char *print_A(char *dst, char *end);

static int zero_or_one(void)
{
    int rv = rand() % 2;
    return rv;
}

static char *print_S(char *dst, char *end)
{
    assert(dst <= end);
    if (dst < end)
    {
        if (zero_or_one() == 0)
            *dst++ = '0';
        else
        {
            dst = print_A(dst, end);
            dst = print_A(dst, end);
        }
    }
    *dst = '\0';
    return dst;
}

static char *print_A(char *dst, char *end)
{
    assert(dst <= end);
    if (dst < end)
    {
        if (zero_or_one() == 1)
            *dst++ = '1';
        else
        {
            dst = print_S(dst, end);
            dst = print_S(dst, end);
        }
    }
    *dst = '\0';
    return dst;
}

int main(void)
{
    srand(time(0));
    for (int i = 0; i < 25; i++)
    {
        char buffer[100];
        (void)print_A(buffer, buffer + sizeof(buffer) - 1);
        printf("%s\n", buffer);
        (void)print_S(buffer, buffer + sizeof(buffer) - 1);
        printf("%s\n", buffer);
    }
    return 0;
}

Обратите внимание, что последовательности часто очень короткие, но могут быть и довольно длинными. Один пример запуска:

01011
0
1
0
1
0
00
11
1
0
1
0
1
1110
00
101110101000000011100001110000100111011011000110001000000111010001000110000100010000111111001100011
1
0
11000011111000110011001000011100
0
1
1000000100001000
011
0
110
0
1
0
1
001
1
0110110011000
11110011110101100101100000111101011010001000110110010100011001100
10111001100101
1
100
100010
0
00
0
011
11
0000100010110
0
1
11
00
0
1
0

Некоторые прогоны примеров были усечены до 99 символов — как и длинный в этом примере. Я также пробовал с размерами 300 и 1000; в обоих случаях я получил пробные прогоны, которые были усечены.

Если вы хотите сделать динамическое выделение памяти, вы должны быть немного хитрее:

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

/* One of these is sufficient; symmetry requires both */
static char *print_S(char **buffer, size_t *len, char *dst);
static char *print_A(char **buffer, size_t *len, char *dst);

static int zero_or_one(void)
{
    int rv = rand() % 2;
    return rv;
}

static void add_space(char **buffer, size_t *len, char **dst)
{
    assert(*dst < *buffer + *len);
    if (*dst == *buffer + *len - 1)
    {
        char *newbuf = realloc(*buffer, 2 * *len);
        if (newbuf == 0)
        {
            fprintf(stderr, "Out of memory (%zu)\n", 2 * *len);
            exit(1);
        }
        *len *= 2;
        *buffer = newbuf;
        *dst = *buffer + strlen(*buffer);
    }
}

static char *print_S(char **buffer, size_t *len, char *dst)
{
    add_space(buffer, len, &dst);

    if (zero_or_one() == 0)
        *dst++ = '0';
    else
    {
        dst = print_A(buffer, len, dst);
        dst = print_A(buffer, len, dst);
    }
    *dst = '\0';
    return dst;
}

static char *print_A(char **buffer, size_t *len, char *dst)
{
    add_space(buffer, len, &dst);
    if (zero_or_one() == 1)
        *dst++ = '1';
    else
    {
        dst = print_S(buffer, len, dst);
        dst = print_S(buffer, len, dst);
    }
    *dst = '\0';
    return dst;
}

int main(void)
{
    srand(time(0));
    size_t len = 100;
    char *buffer = malloc(len);
    for (int i = 0; i < 25; i++)
    {
        (void)print_A(&buffer, &len, buffer);
        printf("%zu: %s\n", strlen(buffer), buffer);
        (void)print_S(&buffer, &len, buffer);
        printf("%zu: %s\n", strlen(buffer), buffer);
    }
    free(buffer);
    return 0;
}

При этом я получил один запуск, в котором длина выходной строки составляла 14 473 874 байта. Я не буду печатать его здесь; достаточно сказать, что в нем были 1 и 0.