Recursion can be fast enough if you cache the results.

The problem may be that when you allocate your char array with c = (char *)malloc(sizeof(char) * (i + 1));, you are not setting the last element c[i] to 0 (or '\0'). Remember that malloc does not initialize any memory, it only allocates it (but calloc will initialize to 0). This can cause a problem with strcmp since it compares the strings up until it reaches 0 on one or both of them.

incredible

lol what

This is not a well tested kata. Some of the test cases are off by one in Racket. It seems like some expect the population to be greater or equal than the desired one, but some expect it to be greater.

This shouldn't be a solution, although it's very clever how you gamed the system.