Recursion or iteration (was Fibonacci series recursion error)

[Chris Angelico]

On Tue, May 3, 2011 at 11:48 AM, rusi <rustompmody at gmail.com> wrote:
> What are their space/time complexities?
> Which do you prefer?

They're pretty similar actually. If you rework the first one to not
use range() but instead have a more classic C style of loop, they'll
be almost identical:

def powI(x,n):
   result = 1
   while n > 0:
       result *= x
       n-=1
   return result

There's a subtle difference in that powR as you've coded it will
infinite-loop if given a negative exponent, while powI in any form
will simply return 1 (neither is technically correct, fwiw). Other
than that, the only difference is that one keeps its state on the call
stack, the other uses a temporary variable.

Performance would probably benefit from a special syntax meaning
"recurse", which would avoid the LOAD_GLOBAL for the function's name
(plus, things break if you pass recursive functions around after
compiling them - for instance, powR2=powR; def powR(x,n): os.exit() -
but if you do that, then you should expect to see nice bullet-holes in
your foot). However, I do not believe that Python would overall
benefit from any such thing.

Chris Angelico