To use the language of Ableson and Sussman in Structure and Interpretation of Computer Programs [node 15]:
The fast doubling algorithm has a recursive definition and produces a logarithmic procedure.
The classic implementation based on the mathematical definition:
def F(n):
if n == 0: return 0
elif n == 1: return 1
else: return F(n-1)+F(n-2)
Has a recursive definition and produces a recursive procedure [even worse the recursive procedure runs in exponential time]. It is also possible to create a recursive definition of a procedure that runs in linear time.
The fast doubling algorithm has a recursive definition and produces a logarithmic procedure.
The classic implementation based on the mathematical definition:
Has a recursive definition and produces a recursive procedure [even worse the recursive procedure runs in exponential time]. It is also possible to create a recursive definition of a procedure that runs in linear time.[node 15]: https://mitpress.mit.edu/sicp/full-text/sicp/book/node15.htm...