Der einzige Grund warum eine rekursive Lösung unter Umständen einen leichten Performance-/Speicheroverhead hat liegt
in der Rechnerarchitektur begründet, ansonsten wird es zwischen beiden keinen Unterschied geben.
Ganz bestimmt nicht. Die Komplexität bzw. Effizienz von Algorithmen hat zunächst einmal überhaupt nichts mit ihrer Umsetzung zu tun.
Außerdem wurde mit der rekursiven Berechnung irgendeines Gliedes der Fibonacci-Folge diese pauschale Lobhudelei der Rekursion bereits widerlegt, denn dort wird jeder Zwischenwert doppelt, dreimal oder noch (viel) häufiger berechnet.