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 _______________________________________________ Wikitech-l mailing list [email protected] https://lists.wikimedia.org/mailman/listinfo/wikitech-l
