3 ms·
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
by 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 agoAgreed, 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 agoevery 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 agoVery Sussman-y. His distate for ambiguity is very coherent.