I build a C++ code with autotools i.e. ./configure && make && make install, but now I want to change the directory where the code installs so I should do ./configure --prefix=${INSTALL_DIR} && make && make install.
Does this now recompile the whole code (I would like to avoid this at all cost) and if so are there other options?
I have heard about the export DESTDIR="${INSTALL_DIR}" && make install trick, but I have also heard that this keeps somehow the reference to the install directory and as well a relative path in the binary. So far I have not found a good explanation of the difference of the two approaches anywhere
We cannot tell you any of the answers to these questions because they all depend 100% on your project and how it's configured. Did you actually try to run the above commands? What happened? That's for more useful information, and much more readily available, than asking us what will happen.
In most autoconf projects ./configure will create a header file config.h which contains the configuration, and in most projects that header is included by all the source files, so modifying that file will indeed cause everything to be rebuilt.
In most autoconf projects, the config.h file won't be updated (and so nothing will be rebuilt) unless its contents change.
In some autoconf projects the prefix directory is provided as a #define in the config.h file, and so in those autoconf projects if you change the value of --prefix then config.h will be updated and all the code will be rebuilt.
Whether your project falls with in the category of "most" and "some" above, only you can say.
As for the difference between --prefix and DESTDIR, you've already discovered it: the value of --prefix is set at configure time and could be (depending on the project) compiled into the code itself as a hardcoded path (but this is generally considered not desirable: projects should either use relative paths or, where not possible, provide some environment variable or option to reset this path).
DESTDIR is not available at compile time, and is an install-time setting that only changes where the makefiles will copy files to, without changing any compiled-in paths that were set by --prefix.