Fibonacci - recursividade

http://en.wikipedia.org/wiki/Fibonacci_word

Pegando a ideia da wikipedia. Não fiz recursivo.

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

char * palavra;

void replace_all_b() {
for(size_t i=0; i<strlen(palavra); i++) {

 if (palavra[i] == 'b') palavra[i] = '?';
	}
}

unsigned int contar_a() {

	unsigned int contagem = 0;
	for(size_t i=0; i<strlen(palavra); i++) {
 if (palavra[i] == 'a') contagem++;
	}
	return contagem;
}

void replace_all_a() {

	unsigned int qtde_a = contar_a();
	size_t novo_tamanho = strlen(palavra) + qtde_a + 1; // Cada letra 'a' gera duas letras, então somamos novamente a quantidade de 'a' na string.
	char * nova_palavra = malloc(novo_tamanho * sizeof(char));

	for(size_t i=0,j=0; i<strlen(palavra); i++) {
 if (palavra[i] == 'a') {
 nova_palavra[j] = 'a';
 nova_palavra[j+1] = 'b';
 j+=2;
 } else {
 nova_palavra[j] = palavra[i];
 j++;
 }
	}
	palavra = realloc(palavra, novo_tamanho * sizeof(char));
	strncpy(palavra, nova_palavra, novo_tamanho-1);
	palavra[novo_tamanho-1] = '\0';

	free(nova_palavra);
	nova_palavra = NULL;
}

void replace_all_question() {
for(size_t i=0; i<strlen(palavra); i++) {

 if (palavra[i] == '?')
 palavra[i] = 'a';
	}
}

void fib_word(unsigned int N) {
/ 'a' vira 'ab'. 'b' é trocado por 'a' /

	for(unsigned int i=0; i<N; i++) {
 replace_all_b();
 replace_all_a();
 replace_all_question();
	}
}

int main(void) {

	unsigned int N;
	scanf("%u", &N);

	palavra = malloc(sizeof(char)*2);
	palavra[0] = 'b';
	palavra[1] = '\0';

	if (N) {
 fib_word(N);
	}

	printf("%s\n", palavra);
	free(palavra);
	return 0;
}

Só tem que tomar cuidado p/ não estourar o heap.

A ideia principal está aí na forma iterativa. Você pode criar uma forma recursiva iniciando do i=0 até i<N (caso você comece de N não vai ser possível gerar a string dessa forma).