Iteration over recursion?

[MTD]

Hello all,

I've been messing about for fun creating a trial division factorizing
function and I'm naturally interested in optimising it as much as
possible.

I've been told that iteration in python is generally more
time-efficient than recursion. Is that true?

Here is my algorithm as it stands. Any suggestions appreciated!

from math import *

def factorize(x):
""" Return factors of x """
factors = []
lim = int(sqrt(x))
y = divmod(x,2)
if y[1] == 0: # x is even
factors = factors + [2] + factorize(y[0])
else: # x is odd
i = 3
while i <= lim:
y = divmod(x,i)
if y[1] == 0:
factors = factors + [i] + factorize(y[0])
i = lim+1
else:
i += 2

if factors == []: # necessary step for correct recursion
factors = [x]

return factors

[Jon Clements]

Re: Iteration over recursion?


MTD wrote:[color=blue]
> Hello all,
>[/color]

(snip)
[color=blue]
> I've been told that iteration in python is generally more
> time-efficient than recursion. Is that true?[/color]

(snip)

AFAIK, in most languages it's a memory thing. Each time a function
calls itself, the 'state' of that function has to be stored somewhere
so that it may continue, as was, when the recursive function returns.
Therefore, you can effectively think of it as creating N many objects
which don't start getting released until the very last nested call
returns. This (depending on the stack size and implementation etc...)
may force several memory allocations. Then of course, as it starts
going back 'upwards' (towards the initiator of the recursive call that
is), the garbage collector may kick in freeing memory...

Depending on return values, iterating will just require space for the
returned value from each function in term (which in most cases - I
would imagine fits on the stack), so although it's doing effectively
the same thing, it's doing so with less memory.

I probably haven't explained too well, and I may not even be right. So
take with a pinch of salt.

All the best,

Jon.

[Nick Maclaren]

Re: Iteration over recursion?


In article <1150816827.826 028.114740@h76g 2000cwa.googleg roups.com>,
"Jon Clements" <joncle@googlem ail.com> writes:
|> MTD wrote:
|>
|> > I've been told that iteration in python is generally more
|> > time-efficient than recursion. Is that true?
|>
|> AFAIK, in most languages it's a memory thing. Each time a function
|> calls itself, the 'state' of that function has to be stored somewhere
|> so that it may continue, as was, when the recursive function returns.

Well, vaguely. That is probably the case in Python, but it isn't always
true, and is not the only issue.

Tail recursion removal can often eliminate the memory drain, but the
code has to be written so that will work - and I don't know offhand
whether Python does it.

In compiled "3rd GL" languages, there are a lot of optimisation issues
where iteration will often produce better code than recursion, but few
(if any) are relevant to Python.


Regards,
Nick Maclaren.

[Bruno Desthuilliers]

Re: Iteration over recursion?

Nick Maclaren wrote:
(snip)[color=blue]
> Tail recursion removal can often eliminate the memory drain, but the
> code has to be written so that will work - and I don't know offhand
> whether Python does it.[/color]

It doesn't. Technical possible, but BDFL's decision...



--
bruno desthuilliers
python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in 'onurb@xiludom. gro'.split('@')])"

[Sudden Disruption]

Re: Iteration over recursion?

Bruno,
[color=blue]
> It doesn't. Technical possible, but BDFL's decision...[/color]

Sure. But why bother?

Anything that can be done with recursion can be done with iteration.
Turng proved that in 1936.

Recursion was just an attempt to "unify" design approach by abstracting
itteration and creating a new context. It allowed the programmer to
isolate himself from the reality that he was actually iterating. Talk
about mind fuck.

It seems things were just to simple the way they were.

Like all fashion, this too shall pass.


Sudden Disruption
--
Sudden View...
the radical option for editing text

http://www.sudden.net/

http://suddendisruption.blogspot.com

[Kay Schluehr]

Re: Iteration over recursion?

Nick Maclaren wrote:
[color=blue]
> Tail recursion removal can often eliminate the memory drain, but the
> code has to be written so that will work - and I don't know offhand
> whether Python does it.[/color]

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691

Regards,
Kay

[Jon Clements]

Re: Iteration over recursion?


Sudden Disruption wrote:
[color=blue]
> Bruno,
>[color=green]
> > It doesn't. Technical possible, but BDFL's decision...[/color]
>
> Sure. But why bother?
>[/color]

I agree.
[color=blue]
> Anything that can be done with recursion can be done with iteration.
> Turng proved that in 1936.
>
> Recursion was just an attempt to "unify" design approach by abstracting
> itteration and creating a new context. It allowed the programmer to
> isolate himself from the reality that he was actually iterating. Talk
> about mind fuck.
>[/color]

Well, unless I'm seriously mistaken, it also breaks good design. If a
function calls another function, it's because it requires that
function's specific service. If the service it requires is itself, then
the function should iterate over a set of data and accumulate/reduce
or whatever else it needs to do. As well as that, I can imagine
exception handling becoming quite cumbersome/clumsy.

[color=blue]
> It seems things were just to simple the way they were.
>
> Like all fashion, this too shall pass.[/color]

Be great if it does; but I don't imagine this will happen until
examples of traversing a binary tree using recursion disappear from
computer science text books (the ones I have seen anyway...). Unless,
later in the course (they might do this, I don't know for sure), they
then say, "BTW people, this is the correct way to do it, because the
previous way isn't too good an idea...".

[color=blue]
> Sudden Disruption
> --
> Sudden View...
> the radical option for editing text
> http://www.sudden.net/
> http://suddendisruption.blogspot.com[/color]

Just my little rant,

Jon.

[Bruno Desthuilliers]

Re: Iteration over recursion?

Sudden Disruption a écrit :[color=blue]
> Bruno,
>
>[color=green]
>>It doesn't. Technical possible, but BDFL's decision...[/color]
>
>
> Sure. But why bother?[/color]

Because I do like recursion, and would personnally prefer tail-recursion
optimisation over nice tracebacks. But I'm not in position to decide
anything here.
[color=blue]
> Anything that can be done with recursion can be done with iteration.
> Turng proved that in 1936.[/color]

Yes. And everything done with Python can be done with assembly language
too.
[color=blue]
> Recursion was just an attempt to "unify" design approach by abstracting
> itteration and creating a new context. It allowed the programmer to
> isolate himself from the reality that he was actually iterating. Talk
> about mind fuck.[/color]

Recursion is the most convenient way to express some common algorithms.
Too bad for you if it does some nasty things to your mind.

[Jon Clements]

Re: Iteration over recursion?


Kay Schluehr wrote:
[color=blue]
> Nick Maclaren wrote:
>[color=green]
> > Tail recursion removal can often eliminate the memory drain, but the
> > code has to be written so that will work - and I don't know offhand
> > whether Python does it.[/color]
>
> http://aspn.activestate.com/ASPN/Coo.../Recipe/496691
>
> Regards,
> Kay[/color]

Interesting.... .

Thanks Kay.

Jon.

[Nick Maclaren]

Re: Iteration over recursion?


In article <449846e0$0$479 3$636a55ce@news .free.fr>,
Bruno Desthuilliers <bdesth.quelque chose@free.quel quepart.fr> writes:
|> Sudden Disruption a écrit :
|>
|> Because I do like recursion, and would personnally prefer tail-recursion
|> optimisation over nice tracebacks. But I'm not in position to decide
|> anything here.

[ See below before you jump to conclusions :-) ]

If you have ever had to unpick a really nasty problem where tail recursion
removal has destroyed all evidence of how the program got there AND the
program was written so that it plain did not work without it (memory
exhaustion), you will have cursed the concept to hell and back again.
Been there - done that :-(

|> > Recursion was just an attempt to "unify" design approach by abstracting
|> > itteration and creating a new context. It allowed the programmer to
|> > isolate himself from the reality that he was actually iterating. Talk
|> > about mind fuck.

As someone who was in this area when the Algol versus Fortran wars were
being fought, that is almost entirely incorrect. Recursion plus tail
removal AS A SUBSTITUTE FOR ITERATION is what you are describing, but
that came a decade after recursion became widespread in programming
languages.

|> Recursion is the most convenient way to express some common algorithms.
|> Too bad for you if it does some nasty things to your mind.

Agreed. Recursion should be used when it is the right technology to
clarify the code, and not as a gimmicky, obfuscatory and often dogmatic
substitute for iteration! There are algorithms that become almost
incomprehensibl e without recursion, and I have implemented a recursion
layer in both assembler AND Fortran just to enable me to write them
without going bonkers.


Regards,
Nick Maclaren.

[Tim Peters]

Re: Iteration over recursion?

[MTD][color=blue]
> I've been messing about for fun creating a trial division factorizing
> function and I'm naturally interested in optimising it as much as
> possible.
>
> I've been told that iteration in python is generally more
> time-efficient than recursion. Is that true?[/color]

Since you heard it from me to begin with, I suppose saying "yes" again
won't really help ;-) You can use time.time() or time.clock(), or the
`timeit` module, to measure speed. Try timing a dead-simple factorial
functions both ways.

BTW, I've worked on Python's implementation for close to 15 years now,
so when I say something about Python, it's _usually_ safe to just
believe it :-) Questioning is fine, but in cases like this where it's
easy to find out for yourself, I probably won't make time to respond.
[color=blue]
> Here is my algorithm as it stands. Any suggestions appreciated!
>
> from math import *
>
> def factorize(x):
> """ Return factors of x """
> factors = []
> lim = int(sqrt(x))[/color]

Here you're limited to integers for which a floating sqrt is accurate.
That's 53 bits on most platforms. For integers larger than that, the
code may produce incorrect results in mysterious ways at times
(because the square root may be inaccurate).
[color=blue]
> y = divmod(x,2)[/color]

Most people would use "unpacking assignment" here instead, like

q, r = divmod(x, 2)

Then later code gets to use meaningful names instead of messing with
mysterious little integer subscripts. It's also quicker to use local
names than to build subscripting expressions.
[color=blue]
> if y[1] == 0: # x is even
> factors = factors + [2] + factorize(y[0])[/color]

Since `factors` upon entry to this block must be [], it's kinda
contorted. More obvious (if you _have_ to use recursion) would be:

return [2] + factorize(y[0])

and then unindent the rest of the code a level.
[color=blue]
> else: # x is odd
> i = 3
> while i <= lim:
> y = divmod(x,i)[/color]

Again more commonly written:

q, r = divmod(x, i)
[color=blue]
> if y[1] == 0:
> factors = factors + [i] + factorize(y[0])[/color]

It hardly matters in this context, but appending to a list is
_generally_ much faster than building a brand new list from scratch.

At a higher level, your recursions always start from 2 again; e.g., if
i happens to be 434349 here, the factorize(y[0]) call starts over from
2, despite that you already know that no divisor less than 434349 can
succeed. To do this _efficiently_ with recursion requires passing
more knowledge across recursion levels.
[color=blue]
> i = lim+1
> else:
> i += 2
>
> if factors == []: # necessary step for correct recursion
> factors = [x]
>
> return factors[/color]

Recursion is pretty bizarre here. Not _wrong_, just "pretty bizarre",
and is leading you into higher-level inefficiences. There are all
sorts of ways to repair that, but I'm not going to talk about them
because it's easy to write an iterative algorithm instead.

Here's one way to do that, avoiding float sqrt (this works correctly
for integers of any size, although trial division is hopelessly
_inefficient_ for finding "large" factors), and skipping multiples of
3 in the inner loop too:

def trial(n):
if n <= 1:
return [n]
factors = []
for tiny in 2, 3:
while n % tiny == 0:
factors.append( tiny)
n //= tiny
delta = 2
d = 5
while 1:
q, r = divmod(n, d)
if r:
if q < d:
break
d += delta
delta = 6 - delta
else:
factors.append( d)
n = q
if n > 1:
factors.append( n)
return factors

If we call the original input N, the key invariants holding at the top
of the loop are:

1. N >= 2, and N == n * the product of the integers in `factors`
2. n is not divisible by any prime < d
3. all elements in `factors` are prime

It may take a bit of thought to see that d marches over all integers[color=blue]
>= 5 that aren't divisible by either 2 or 3: 5, 7, 11, 13, 17, 19,[/color]
23, 25, 29, 31, ...

It's more-or-less generally true that establishing and proving loop
invariants in an iterative algorithm is "the same thing" as
establishing and proving pre- and post-conditions in a recursive
algorithm. While it may feel strained at first, it's very much
worthwhile learning how to do that. For example, from #2 it's easy to
prove that if q < d, n must either be 1 or a prime. That's what
justifies the "break" statement inside the loop. Then since that's
the only way to get out of the loop, n is either 1 or a prime when the
loop finishes, and that explains the rest of the code.

[Sudden Disruption]

Re: Iteration over recursion?

Bruno,
[color=blue]
> Yes. And everything done with Python can be done with assembly language
> too.[/color]

It's even more general than that...

To simply Turning, anything that can compute, can compute anything that
can be computed - hardware OR software.

But that doesn't mean you should use it. Imagine if we all took that
to heart and only coded for the Turing Machine!

So yes, I'll concede the point. Some tools ARE better than others.
It's just that recursion is more often misused than not.
[color=blue]
> Recursion is the most convenient way to express some common algorithms.[/color]

Yes. But very few.
[color=blue]
> Too bad for you if it does some nasty things to your mind.[/color]

It's not recursion per se that does the nasty things. It's the way
it's been promoted over the years when the simplier iterative solution
is a better choice.


Sudden Disruption
--
Sudden View...
the radical option for editing text

http://www.sudden.net/

http://suddendisruption.blogspot.com

[MTD]

Re: Iteration over recursion?

Thanks a lot! More food for thought!

[Sudden Disruption]

Re: Iteration over recursion?

Nick,
[color=blue]
> you will have cursed the concept to hell and back again. Been there - done that :-([/color]

My point exactly. Years ago with Pascal I took the recursive approach
way too often with much distress. I began to learn that if I move
enough stuff out of the loop and set up a context that could easily see
what was getting "re-cursed" (great term), iteration was often much
easier to debug and FAR more effective to execute.

Since those times I can count on one hand the times I've used recursion
- and then only because I was late for lunch and I knew "i" wouldn't
get away from me.
[color=blue]
> As someone who was in this area when the Algol versus Fortran wars were[/color]

I'll take your word for it. My start with recursion was Pascal.
[color=blue]
> Agreed. Recursion should be used when it is the right technology to
> clarify the code, and not as a gimmicky, obfuscatory and often dogmatic
> substitute for iteration![/color]

Well put.
[color=blue]
> There are algorithms that become almost incomprehensibl e without recursion, and I
> have implemented a recursion layer in both assembler AND Fortran just to enable me
> to write them without going bonkers.[/color]

With a reasonable exception.


Sudden Disruption
--
Sudden View...
the radical option for editing text

http://www.sudden.net/

http://suddendisruption.blogspot.com

[Kay Schluehr]

Re: Iteration over recursion?

You might use a separate prime generator to produce prime factors. The
factorize algorithm becomes quite simple and configurable by prime
generators. For demonstration purposes I use the eratosthenes sieve.

def eratosthenes():
memo = {}
q = 2
while True:
p = memo.pop(q, None)
if p is None:
yield q
memo[q*q] = q
else:
x = p + q
while x in memo:
x += p
memo[x] = p
q+=1

def factorize(n, sieve = eratosthenes):
if n <= 1:
return [n]
factors = []
primes = sieve()
for q in primes:
while n % q == 0:
factors.append( q)
n //= q
if n == 1:
return factors

Regards,
Kay