3 ms·
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
by 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 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.