Re: Why is recursion so slow?



Dan Upton wrote:
On Sun, Jun 29, 2008 at 1:27 AM, Terry Reedy <tjreedy@xxxxxxxx> wrote:

slix wrote:
Recursion is awesome for writing some functions, like searching trees
etc but wow how can it be THAT much slower for computing fibonacci-
numbers?
The comparison below has nothing to do with recursion versus iteration. (It
is a common myth.) You (as have others) are comparing an exponential,
O(1.6**n), algorithm with a linear, O(n), algorithm.


FWIW, though, it's entirely possible for a recursive algorithm with
the same asymptotic runtime to be wall-clock slower, just because of
all the extra work involved in setting up and tearing down stack
frames and executing call/return instructions.

Which is exactly why I continued with "In Python, an algorithm written with iteration is faster than the same algorithm written with recursion because of the cost of function calls. But the difference should be a multiplicative factor that is nearly constant for different n. (I plan to do experiments to pin this down better.) Consequently, algorithms that can easily be written iteratively, especially using for loops, usually are in Python programs."

People should read posts to the end before replying, in case it actually says what one thinks it should, but just in a different order than one expected.

If each call does only a small amount of work, as with fib(), I would guess that time difference might be a factor of 2. As I said, I might do some measurement sometime in order to get a better handle on when rewriting recursion as iteration is worthwhile.

tjr

.

Relevant Pages

  • Short koan-like code snippets (was: coerce for arbitrary types)
    ... (defun bfs6 (test children pending) ... The algorithm seems to be a tail-recursive expression of what ... I don't like using tail recursion to emulate iteration, ...
    (comp.lang.lisp)
  • Re: Software bugs arent inevitable
    ... I suggested that for a given algorithm implemented ... iteration should always be faster by a small factor. ... > recursive function can run out of stack space while the heap still has ... Which is why, in the part you snipped, I said that recursion (unlike ...
    (comp.lang.python)
  • Re: Software bugs arent inevitable
    ... >> resource-requirement differences between iteration and recursion can be ... make the difference between an elegant solution that runs like a lame duck ... floats have a finite precision will cause that algorithm to give incorrect ...
    (comp.lang.python)
  • Re: newbie question: recursion algorithm and iterative algorithm
    ... > "In addition he says that every recursion algorithm can be translated ... Or the existance is proved but transform ... Good compilers often transform tail recursion into iteration. ...
    (comp.lang.prolog)
  • Re: Why is recursion so slow?
    ... etc but wow how can it be THAT much slower for computing fibonacci- ... The comparison below has nothing to do with recursion versus iteration. ... O, algorithm with a linear, O, algorithm. ...
    (comp.lang.python)