Having to deal with dependencies in Makefile is a real pain, there are a lot of examples of way to deal with it on the web but none of them is satisfying.
For example using gcc -MM does not work with subfolders, a depend rule requires the user to use it everytimes he adds new files ...
Here is what is wanted:
- Completly automatic: No user interaction is required when adding new files
 - Works with an arbitrary amount of files
 - Works with an arbitrary amount of level of folders
 - Is not recalculated when nothing changed
 - Use only one file to store dependencies
 - Do not depend on complicated regular expressions
 
Here is the result:
BINARY = project.exe CC = gcc CFLAGS = FILES = $(shell find src/ -name "*.c") HEADERS = $(shell find src/ -name "*.h") OBJS = $(FILES:.c=.o) all: $(BINARY) -include Makefile.deps $(BINARY): Makefile.deps $(OBJS) $(CC) $(CFLAGS) $(OBJS) -o $(BINARY) Makefile.deps: $(FILES) $(HEADERS) makedepend -- $(CFLAGS) -- $(FILES) -f- > Makefile.deps  | 
This is in fact really easy. In your $(BINARY) rule, you add Makefile.deps as a prerequisite.
In order to generate the Makefile.deps you mark all $(FILES) and $(HEADERS) as prerequisite, so every time you change a file or header it will recompile the list.
We use makedepend to generate the dependencies list. It works like gcc -MM except that it outputs the correct file path when used with folders.
Then all is required is to include the Makefile.deps. We include it with -include so it does work the first time you compile.
Thanks to Lemoine Gauthier who helped me to discover this technique.