Hacker News Reader

Comment by spoonman1 | Hacker News Reader

Maybe someone can help me understand a bit better. The author talks about how slow a recursive algorithm is, but the "fast doubling" implementation itself uses recursion. Would not the same slower effect be felt by this implementation due to its use of recursion?

View on HN

The author is not saying "every algorithm which uses recursion is slow".

The author is saying that the naive recursive algorithm is incredibly slow. That would be an implementation like this (in Python):

    def fib(n):
        if n < 2:
            return n
        else:
            return fib(n-1) + fib(n-2)

And that implementation is slow. It's exponentially slow.

Agreed, this response is exactly correct. I didn't realize that my wording of "slow recursion" could be misread as "every recursion is slow", which is not true - especially because every iterative procedure can be expressed as a recursive procedure with the same time complexity.

As a side note, the Java and C# implementations of the "fast doubling" algorithm actually used a fixed number of loop iterations instead of the mathematical recursive formula.

every iterative procedure can be expressed as a recursive procedure.

To use Ableson's precise language:

   Every iterative procedure can be expressed as
   a recursive *definition.*

SICP is written to carefully avoid overloading terms: "Function" is reserved for mathematical functions and "closure" is reserved for algebraic closure.

Very Sussman-y. His distate for ambiguity is very coherent.

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.

[node 15]: https://mitpress.mit.edu/sicp/full-text/sicp/book/node15.htm...

In fact SICP covers the fast doubling fibonacci algorithm directly in exercise 1.19[1] (although in a slightly obfuscated form)

[1] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...

Much appreciated, thank you.

Reply on news.ycombinator.com