// Arup Guha
// 4/29/2022
// Solution to Spring 2022 COP 3502 Final Exam Question 12

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

char* f(int n);

int main(void) {

    // Simple test.
    char* final = f(5);
    printf("%s\n", final);
    free(final);
    return 0;
}

// Returns the string defined in question 12 for the input value n.
char* f(int n) {

    // Amount of space to allocate.
    char* res = malloc(sizeof(char)*(1<<(n+1)));

    // First character is the nth character (0-based).
    res[0] = (char)('a'+n);
    res[1] = '\0';

    // We're done if n is 0...
    if (n == 0) return res;

    // Otherwise we recursively generate the n-1 string.
    char* tmp = f(n-1);

    // Then just concatenate it twice.
    strcat(res, tmp);
    strcat(res, tmp);

    // Now that everything is in res, we free this.
    free(tmp);

    // Ta da!
    return res;
}