Rekursive Algorithmen haben immer einen gewissen Overhead. Manchmal ist diser unvermeidbar, manchmal lässt er sich durch Konvertierung in einen Schleifenalgorithmus oder TailRecursion reduzieren.

Ich würde nicht sagen, dass ein Algorithmus einen Overhead haben kann. Eine Implementation kann einen Overhead haben. Dabei mag obige Aussage für Implementationen in C und anderen ähnlichen Sprachen gelten, aber nicht für Implementationen in deklarativen Programmiersprachen.