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.
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