"Steven D'Aprano" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > Which works wonderfully as an academic exercise, but doesn't tend to work > so terribly well in the real world where the performance and > resource-requirement differences between iteration and recursion can be > significant.
I think your comparison is incomplete. Recursion and iteration are two syntaxes for the same operation: repetition with variation. Indeed, iteration can be viewed as within-frame tail recursion. Recursion usually takes more space for a stack of call frames -- unless the particular system optimizes the stack away for particular functions (by recursing within a frame!). For a given algorithm -- defined by what actually gets computed -- the time difference is a small constant. For Python, recursion is probably slower relative to iteration than for other languages because of the flexibility and slowness of function calls. > For instance, try these two simple functions for the nth number > in the Fibonacci sequence: Abstractly, these are two algorithms for the same function. One runs in exponential time because it wastefully calculates and tosses away an exponential number of subvalues. The other runs in linear time because it calculates each subvalue once. When one only wants Fib(n), and not the sequence leading up to it, even this is wasteful, for large enough n, since there is a third algorithm that caluculates Fib(n) directly by a simple formula (something like the interger part of the golden ratio to the nth power). Now: I could (and probably someday will) write an iterative version of the exponential algorithm (using an explicit stack) that calculates each subvalue exactly as many times as the recursive version of that same algorithm. And I could compare it to a recursive version of the more efficient linear algorithm (such as posted by Jerzy Karczmarczuk). And I could claim that this shows hows iteration can waste time compared to recursion. But that, I admit, would be an invalid conclusion. And that, I claim, is also invalid when 'iteration' and 'recursion' are reversed, no matter how often repeated in texts and articles. The difference is between the algorithms, not the differing syntactic expressions thereof. Terry J. Reedy -- http://mail.python.org/mailman/listinfo/python-list
