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

void fib_string_print(int);
char* fib_string(int);
int fib_str_len(int);


int main()
{
	char *ps;
	ps = fib_string(10);
	printf("%s\n",ps);
	free(ps);
}

void fib_string_print(int n)
{
	switch(n)
	{
		case 0:
			printf("a");
			break;
		case 1:
			printf("ab");
			break;
		default:
			fib_string_print(n-1);
			fib_string_print(n-2);
			break;
	}
}

char* fib_string(int n)
{
	char *f1,*f2,*fn,*temp;
	int i, duzina;
	
	duzina = fib_str_len(n);
	
	if((f1=(char*)malloc(duzina))==NULL)
		exit(1);
		
	if((f2=(char*)malloc(duzina))==NULL)
	{
		free(f1);
		exit(2);
	}
	if((fn=(char*)malloc(duzina))==NULL)
	{
		free(f1);
		free(f2);
		exit(3);
	}
	
	strcpy(f1,"a");
	strcpy(f2,"ab");
	
	for(i=2;i<n;i++)
	{
		
		strcpy(fn,f1);
		strcat(fn,f2);	
		printf("%s %d\n",fn,i+1);
		if(i<(n-1)) 
		{
			temp=f1;
			f1=f2;
			f2=fn;
			fn=temp;
		}
		
		
	}
	
	free(f1);
	free(f2);
	
	return fn;
	
} 

int fib_str_len(int n)
{
	int n1=1,n2=1,rezultat=2;
	
	while(n-->2)
	{
		rezultat = n1+n2;
		n2=rezultat;
		n1=n2;
	}
	
	return rezultat;
}