5 ms·

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

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?

ubernostrum 12y ago
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.
- nayuki 12y ago
  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.
  - brudgers 12y ago
    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.
    - agumonkey 12y ago
      Very Sussman-y. His distate for ambiguity is very coherent.
brudgers 12y ago
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.html https://mitpress.mit.edu/sicp/full-text/sicp/book/node15.htm...
- bhrgunatha 12y ago
  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#%_thm_1.19 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...
- spoonman1 12y ago
  Much appreciated, thank you.

ubernostrum 12y ago

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.

nayuki 12y ago
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.
- brudgers 12y ago
  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.
  - agumonkey 12y ago
    Very Sussman-y. His distate for ambiguity is very coherent.

brudgers 12y ago

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.html https://mitpress.mit.edu/sicp/full-text/sicp/book/node15.htm...

bhrgunatha 12y ago
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#%_thm_1.19 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...
spoonman1 12y ago
Much appreciated, thank you.