Steve Sanbeg wrote:
On Fri, 03 Jul 2009 17:13:45 +1000, Tim Starling wrote:
Recursion can give a long running time even if the depth is limited. By calling the function multiple times from its own body, you can have exponential time order in the recursion depth.
All those calls still end up on the same stack; even if it could be a tree in theory, the stack only grows one way, and execution time would only be linear.
That's an interesting theory.
I found some documentation on the example I'd thought of emulating, which may clarify a little:
http://www.delorie.com/gnu/docs/elisp-manual-21/elisp_123.html
I thought I would try it.
(defun pow5 (n) (if (= n 0) 1 (+ (pow5 (1- n)) (pow5 (1- n)) (pow5 (1- n)) (pow5 (1- n)) (pow5 (1- n)) ) ) )
It calculates 5 to the power of n by adding 1+1+1+1+1... I found that with a stack depth limit of 25, I was able to calculate 5^6 = 15625. That's plainly not an O(N) execution time in stack depth.
-- Tim Starling