Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #4182 > unrolled thread

Re: Fibonacci series recursion error

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Fibonacci series recursion error Paul Rudin <paul.nospam@rudin.co.uk> - 2011-04-30 15:40 +0100
    Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-01 09:18 +0100
      Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-01 09:04 +0000
        Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-01 10:27 +0100
          Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-01 11:56 +0000
            Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-01 14:15 +0100
              Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-02 06:49 +1000
                Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 06:36 +0100
                  Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-02 16:28 +1000
                  Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-02 16:30 +1000
                  Re: Fibonacci series recursion error (slightly OT) Dave Angel <davea@ieee.org> - 2011-05-02 08:50 -0400
              Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-02 01:09 +0000
                Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 10:41 +0100
          Re: Fibonacci series recursion error Terry Reedy <tjreedy@udel.edu> - 2011-05-01 18:24 -0400
            Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 14:14 +0100
              Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-02 16:41 +0000
                Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-02 21:02 +0100
                  Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-03 00:21 +0000
                    Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 20:42 -0700
                    Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-03 06:13 +0100
                    Re: Fibonacci series recursion error Robert Brown <robert.brown@gmail.com> - 2011-05-08 01:44 -0400
                      Re: Fibonacci series recursion error Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-08 12:59 +0000
                        Development time vs. runtime performance (was: Fibonacci series recursion error) Teemu Likonen <tlikonen@iki.fi> - 2011-05-08 19:34 +0300
                          Re: Development time vs. runtime performance (was: Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-09 12:49 +1000
                          Re: Development time vs. runtime performance (was: Fibonacci series recursion error) Robert Brown <robert.brown@gmail.com> - 2011-05-08 23:01 -0400
              Re: Fibonacci series recursion error Terry Reedy <tjreedy@udel.edu> - 2011-05-02 14:56 -0400
              Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 07:56 +1000
                Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-05-03 08:01 +0100

Page 1 of 2  [1] 2  Next page →

#4182 — Re: Fibonacci series recursion error

Hans Georg Schaathun <hg@schaathun.net> writes:

> On Sat, 30 Apr 2011 12:29:00 +0100, Paul Rudin
>   <paul.nospam@rudin.co.uk> wrote:
> :  Clearly it makes a difference in any case where you'd hit the recursion
> :  limit.
>
> What kind of problems make you hit the limit?
>
> Other than when you forget the base case, I mean.

Anytime you have enough data... there are plenty of things that are natural to
represent as recursive data structures, and often you don't know in
advance how much data your code is going to have to deal with.

[toc] | [next] | [standalone]

#4379

On Sat, 30 Apr 2011 15:40:24 +0100, Paul Rudin
  <paul.nospam@rudin.co.uk> wrote:
:  Anytime you have enough data... there are plenty of things that are natural to
:  represent as recursive data structures, and often you don't know in
:  advance how much data your code is going to have to deal with.

Sure, but one would think that if you can fit the data in memory,
then you can also fit the call stack.  I can also /imagine/ that one
might run into a limit, but I cannot see any concrete examples where
it is likely.

-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#4384

On Sun, 01 May 2011 09:18:36 +0100, Hans Georg Schaathun wrote:

> On Sat, 30 Apr 2011 15:40:24 +0100, Paul Rudin
>   <paul.nospam@rudin.co.uk> wrote:
> :  Anytime you have enough data... there are plenty of things that are
> natural to :  represent as recursive data structures, and often you
> don't know in :  advance how much data your code is going to have to
> deal with.
> 
> Sure, but one would think that if you can fit the data in memory, then
> you can also fit the call stack.  I can also /imagine/ that one might
> run into a limit, but I cannot see any concrete examples where it is
> likely.


Why? You might have 4000 MB of main memory, and only 2 MB (say?) of call 
stack allocated. The call stack can't grow indefinitely. If it does, you 
get a stack overflow:

http://www.ehow.com/list_6572027_reasons-stack-overflow.html

which, if you're lucky, will just crash the process. If you're unlucky, 
it will lead to an exploit that malware can use to compromise your 
machine.

In Python, the virtual machine protects you against stack overflow. 
Before the stack overflows, Python raises RecursionError. You can 
experiment by using sys.getrecursionlimit and sys.setrecursionlimit, but 
be careful, if you increase the limit too high, a deeply recursive 
function will overflow the stack.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#4386

On 01 May 2011 09:04:27 GMT, Steven D'Aprano
  <steve+comp.lang.python@pearwood.info> wrote:
:  Why? You might have 4000 MB of main memory, and only 2 MB (say?) of call 
:  stack allocated. The call stack can't grow indefinitely. If it does, you 
:  get a stack overflow:

Of course you do, but you are still only saying that there might be 
an application where this might happen because of excessive although
logically correct recursion.  You have not given a single example where 
it actually happened.

:  In Python, the virtual machine protects you against stack overflow. 
:  Before the stack overflows, Python raises RecursionError. You can 
:  experiment by using sys.getrecursionlimit and sys.setrecursionlimit, but 
:  be careful, if you increase the limit too high, a deeply recursive 
:  function will overflow the stack.

But the recursion limit is mainly there to protect you against faulty
base cases.  Obviously, since it measures the number of items on the
stack and not their size.

-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#4388

On Sun, 01 May 2011 10:27:14 +0100, Hans Georg Schaathun wrote:

> On 01 May 2011 09:04:27 GMT, Steven D'Aprano
>   <steve+comp.lang.python@pearwood.info> wrote:
> :  Why? You might have 4000 MB of main memory, and only 2 MB (say?) of
> call :  stack allocated. The call stack can't grow indefinitely. If it
> does, you :  get a stack overflow:
> 
> Of course you do, but you are still only saying that there might be an
> application where this might happen because of excessive although
> logically correct recursion.  You have not given a single example where
> it actually happened.

Just google on "stack overflow crash".


> :  In Python, the virtual machine protects you against stack overflow. :
>  Before the stack overflows, Python raises RecursionError. You can : 
> experiment by using sys.getrecursionlimit and sys.setrecursionlimit, but
> :  be careful, if you increase the limit too high, a deeply recursive : 
> function will overflow the stack.
> 
> But the recursion limit is mainly there to protect you against faulty
> base cases.  Obviously, since it measures the number of items on the
> stack and not their size.

The Python virtual machine knows how big each entry on the stack needs to 
be. (I don't, but it's got to be at least the size of a pointer.) So 
"number of items" is just a multiplication away from "size of the items".

In practice the main reason that stacks overflow is because of faulty 
base cases in recursion. That's obvious. But in principle, any 
sufficiently large number of function calls could overflow the stack. If 
the call stack is (say) 1 MB (chosen only to make the maths easier), and 
each function call requires (say) a single four-byte entry on the stack, 
then you can have a maximum of 250000 function calls before overflowing 
the stack.

If you don't like my numbers -- and you probably shouldn't, since I made 
them up -- choose your own. But whatever numbers you choose, there *must* 
be a maximum number of function calls before the stack overflows.

Not necessarily recursive function calls either: any nested function call 
will do. However, it's generally only in recursion that you have more 
than a few hundred calls on the stack.

So even if the base case is correct, you can overflow the stack. Given 
the naive recursive factorial function:

def fact(n):
    if n <= 1: return 1
    return n*fact(n-1)

and the theoretical limit above, then fact(250001) will overflow the 
stack even though the base case is correct.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#4392

On 01 May 2011 11:56:57 GMT, Steven D'Aprano
  <steve+comp.lang.python@pearwood.info> wrote:
:  Just google on "stack overflow crash".

And I get loads of examples of stack overflows, but I could not see
anybody linking this to logically correct recursion.  Wikipedia, for
instance, mentions two common causes, neither of which has anything
to do with logically correct recursion.  

:  The Python virtual machine knows how big each entry on the stack needs to 
:  be. (I don't, but it's got to be at least the size of a pointer.) So 
:  "number of items" is just a multiplication away from "size of the items".

Does it?  In a conventional stack you need to store all the local
variables for the function as well.  Thus, there is no limit to how
much space a single element on the stack may require.

:                                           But in principle, any 
:  sufficiently large number of function calls could overflow the stack.
:  (...)
:  If you don't like my numbers -- and you probably shouldn't, since I made 
:  them up -- choose your own. But whatever numbers you choose, there *must* 
:  be a maximum number of function calls before the stack overflows.

But all of this is in principle, and does not constitute any valid
reason to avoid recursion in practice.  If you want to argue that
recursion is a bad thing in /practice/ you need a /practical/ argument.

There is also a limit to how far you can usefully recurse over a limited
data structure.

:  def fact(n):
:      if n <= 1: return 1
:      return n*fact(n-1)
: 
:  and the theoretical limit above, then fact(250001) will overflow the 
:  stack even though the base case is correct.

Of course that will overflow, but you are now trying to calculate an
integer of several /million/ bits.  Please suggest me a current-day
application where you would want to have and also be able to use such
a number.

There are many ways to crash a system if you want to.

But if you don't deliberately try to crash it, you are much more
likely to crash it because you allocate to much memory in each step
than because the recursion gets to deep.  Consequently, because recursion
is usually a clearer form of expression than iterative loops, recursion
may actually be /less/ dangerous.


-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#4414

On Sun, May 1, 2011 at 11:15 PM, Hans Georg Schaathun <hg@schaathun.net> wrote:
> :  The Python virtual machine knows how big each entry on the stack needs to
> :  be. (I don't, but it's got to be at least the size of a pointer.) So
> :  "number of items" is just a multiplication away from "size of the items".
>
> Does it?  In a conventional stack you need to store all the local
> variables for the function as well.  Thus, there is no limit to how
> much space a single element on the stack may require.

In anything less than a useless and trivial demo of recursion, there's
going to be some kind of local state for each call (in the case of a
fibonacci or factorial, that would be the number(s) being multiplied).
Whether they go on the stack or elsewhere, that's additional storage
that gets multiplied out.

> There is also a limit to how far you can usefully recurse over a limited
> data structure.

Sure. Serialize this Python object in a way that can be given to, say, PHP:
foo={"asdf":"qwer","zxcv":"1234"}; foo["self"]=[1,2,3,foo]
Recurse from self into the list, recurse from there into a
dictionary... Okay, that's a rather naive recursion and fraught with
risk, but there are more complex examples. And watching for cyclic
references would be O(N*N) as you'd need to maintain a full list of
every PyObject* that you've sighted (talking here from the C API, but
the same consideration applies whichever way you do it).

> There are many ways to crash a system if you want to.
>
> But if you don't deliberately try to crash it, you are much more
> likely to crash it because you allocate to much memory in each step
> than because the recursion gets to deep.  Consequently, because recursion
> is usually a clearer form of expression than iterative loops, recursion
> may actually be /less/ dangerous.

I'm not sure that recursion is clearer. Recursion is a way of
expressing the two rules:

1! = 1
n! = n * (n-1)!

But iteration is a way of expressing this equivalent rule:

n! = 1 * 2 * 3 * ... * n-1 * n

It really depends what you're trying to say.

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#4440

On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
  <rosuav@gmail.com> wrote:
:  Sure. Serialize this Python object in a way that can be given to, say, PHP:
:  foo={"asdf":"qwer","zxcv":"1234"}; foo["self"]=[1,2,3,foo]
:  Recurse from self into the list, recurse from there into a
:  dictionary... Okay, that's a rather naive recursion and fraught with
:  risk, but there are more complex examples. And watching for cyclic
:  references would be O(N*N) as you'd need to maintain a full list of
:  every PyObject* that you've sighted (talking here from the C API, but
:  the same consideration applies whichever way you do it).

Wouldn't cyclic references give infinite recursion?  And remain
infinitive if you recode it iteratively?

:  I'm not sure that recursion is clearer. Recursion is a way of
:  expressing the two rules:
: 
:  1! = 1
:  n! = n * (n-1)!
: 
:  But iteration is a way of expressing this equivalent rule:
: 
:  n! = 1 * 2 * 3 * ... * n-1 * n
: 
:  It really depends what you're trying to say.

True.  There is a place for everything.  However, in the example
above, you can map the recursive definition directly into python
without further ado.  In order to express the one-liner in python,
as iteration, you need to introduce additional elements, namely
a state (index variable).  Hence, recursion is clearer by being
close to the language you would normally use to describe the
problem.

-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#4441

On Mon, May 2, 2011 at 3:36 PM, Hans Georg Schaathun <hg@schaathun.net> wrote:
> On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
>  <rosuav@gmail.com> wrote:
> :  Sure. Serialize this Python object in a way that can be given to, say, PHP:
> :  foo={"asdf":"qwer","zxcv":"1234"}; foo["self"]=[1,2,3,foo]
>
> Wouldn't cyclic references give infinite recursion?  And remain
> infinitive if you recode it iteratively?

Well, I don't know of a decent non-recursive way to process a
recursive structure. Incidentally, this example is almost directly
from some working code of ours; I have a C function that recurses over
a Python dictionary and aborts as soon as it's found "too much" data
(for a fairly arbitrary definition of "too much", but one that's
deliberately designed to prevent infinite recursion). Since every
element in the dictionary can be a list/dict, and every element of
those can be too, there's no non-recursive way to do it, other than by
doing the recursion yourself:

# partly pseudocode
searchme=[foo]
while len(searchme):
  cur=get_next_elem(searchme[-1])
  if cur==end_of_list: searchme[-1:]=[]
  else: if can_be_recursed_into(cur): searchme.append(cur)
  else: output(cur)

This would work, more or less, but it merely trades "true" recursion
for the searchme[] stack. Yes, it's iterative. No, it hasn't abolished
recursion.

> True.  There is a place for everything.  However, in the example
> above, you can map the recursive definition directly into python
> without further ado.  In order to express the one-liner in python,
> as iteration, you need to introduce additional elements, namely
> a state (index variable).  Hence, recursion is clearer by being
> close to the language you would normally use to describe the
> problem.

True, and you could abolish a lot of temporary variables by turning
them into parameters to recursive calls. But you've abolished nothing.

The recursive factorial is very similar to:
reduce(`*,range(1,n+1))
The iterative is very similar to:
reduce(`*,xrange(1,n+1))
One of 'em stacks up all the numbers and the other gets 'em as it
needs 'em. Fundamentally, there's really not a lot of difference. By
piling up the numbers on your stack, you just change the format of
your saved state, you don't actually save anything.

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#4442

On Mon, May 2, 2011 at 4:28 PM, Chris Angelico <rosuav@gmail.com> wrote:
> reduce(`*,range(1,n+1))
> reduce(`*,xrange(1,n+1))

Whoops, forgot which language I was using. Back-tick functions not
being available, these need to be:

reduce(operator.mul,range(1,n+1))
reduce(operator.mul,xrange(1,n+1))

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#4476 — Re: Fibonacci series recursion error (slightly OT)

On 01/-10/-28163 02:59 PM, Chris Angelico wrote:
> On Mon, May 2, 2011 at 3:36 PM, Hans Georg Schaathun<hg@schaathun.net>  wrote:
>> On Mon, 2 May 2011 06:49:41 +1000, Chris Angelico
>>   <rosuav@gmail.com>  wrote:
>> :  Sure. Serialize this Python object in a way that can be given to, say, PHP:
>> :  foo=asdf":"qwer","zxcv":"1234"}; foo["self"]=[1,2,3,foo]
>>
>> Wouldn't cyclic references give infinite recursion?  And remain
>> infinitive if you recode it iteratively?
>
> Well, I don't know of a decent non-recursive way to process a
> recursive structure. Incidentally, this example is almost directly
> from some working code of ours; I have a C function that recurses over
> a Python dictionary and aborts as soon as it's found "too much" data
> (for a fairly arbitrary definition of "too much", but one that's
> deliberately designed to prevent infinite recursion).
> <snip>
>
> Chris Angelico
>

When iterating over a repeatable, potentially infinite sequence of 
distinguishable values, you can safely detect infinitude ;-)  (cycles) 
with a linear overhead (rather than n-squared).

Given a sequence, create two iterators for it.  Start them both at the 
same point, but iterate the second one twice for every time you iterate 
the first one.  If the two ever get the same value, you have a cycle.

In the case of Python objects, you probably want to use an 'is' 
comparison, rather than comparing id() for equal.  But the concept 
works, and easily.

DaveA

[toc] | [prev] | [next] | [standalone]

#4429

On Sun, 01 May 2011 14:15:35 +0100, Hans Georg Schaathun wrote:

> On 01 May 2011 11:56:57 GMT, Steven D'Aprano
>   <steve+comp.lang.python@pearwood.info> wrote:
> :  Just google on "stack overflow crash".
> 
> And I get loads of examples of stack overflows, but I could not see
> anybody linking this to logically correct recursion.  Wikipedia, for
> instance, mentions two common causes, neither of which has anything to
> do with logically correct recursion.

Ah, I see where you're coming from now! You think I'm arguing *against* 
the use of recursion. Not at all. Earlier in this thread, I said:

"Consequently, the naive recursive function is ridiculously slow and 
memory-hungry.

This seems to have give rise to a myth that recursion should be avoided. 
What needs to be avoided is *badly thought out* recursion."

[Emphasis in original.]




> :  The Python virtual machine knows how big each entry on the stack
> needs to :  be. (I don't, but it's got to be at least the size of a
> pointer.) So :  "number of items" is just a multiplication away from
> "size of the items".
> 
> Does it?  In a conventional stack you need to store all the local
> variables for the function as well.  Thus, there is no limit to how much
> space a single element on the stack may require.

To be honest, I don't know what Python does with local variables. But I 
*guess* it uses a constant-sized record which points to the locals, 
because that's how I'd do it :)

I do know that objects in CPython all live in the heap, not on the stack, 
so even if local variables are placed directly on the stack, that's only 
a pointer to the object, not the entire object.


[...]
> But all of this is in principle, and does not constitute any valid
> reason to avoid recursion in practice.  If you want to argue that
> recursion is a bad thing in /practice/ you need a /practical/ argument.

Okay. In *practice*, all else being equal, recursion is less efficient 
than iteration, especially in Python which doesn't optimize tail-
recursion. So if you have a choice between two algorithms which are 
equally simple and clear, and one is recursive and the other uses 
iteration, the one with iteration will be more efficient.

However, and equally in practice, it's unusual to have two equally simple 
algorithms. Usually one or the other will be much simpler than the other, 
and you should avoid "optimizing" code based on hypothetical 
considerations and instead prefer simple code over complicated, unless 
absolutely necessary.

Given a choice between a complicated iterative algorithm and a simple 
recursive version, there's no prima facie reason to expect the recursive 
version to *necessarily* be slower than iteration in Python *merely* 
because it uses recursion. As always, if speed is an issue, profile and 
identify the bottlenecks before deciding how to fix them.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#4466

On 02 May 2011 01:09:21 GMT, Steven D'Aprano
  <steve+comp.lang.python@pearwood.info> wrote:
:  Ah, I see where you're coming from now! You think I'm arguing *against* 
:  the use of recursion. Not at all. Earlier in this thread, I said:

Fair enough.  Somebody said something about recursion mainly being
a beginner's error.  I don't think it was you, but I felt that your
argument in context mainly served to reinforce such a view, whether
intended or not.

:  "Consequently, the naive recursive function is ridiculously slow and 
:  memory-hungry.
: 
:  This seems to have give rise to a myth that recursion should be avoided. 
:  What needs to be avoided is *badly thought out* recursion."

Then we agree.

And badly thought-out iteration is as bad as badly thought-out
recursion.

:  To be honest, I don't know what Python does with local variables. But I 
:  *guess* it uses a constant-sized record which points to the locals, 
:  because that's how I'd do it :)

Maybe, but would it be able to treat specially C API functions with 
a large chunk of stack memory used for local variables?

:  Given a choice between a complicated iterative algorithm and a simple 
:  recursive version, there's no prima facie reason to expect the recursive 
:  version to *necessarily* be slower than iteration in Python *merely* 
:  because it uses recursion. As always, if speed is an issue, profile and 
:  identify the bottlenecks before deciding how to fix them.

Then we are on the same page.

And it is becoming increasingly clear how bizarre this discussion is in 
a python context.  The overhead which may be caused by recursion in
hardware is only one of many sources of overhead which one accepts when 
opting to use python in order to gain other benefits.

-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#4420

On 5/1/2011 5:27 AM, Hans Georg Schaathun wrote:

> Of course you do, but you are still only saying that there might be
> an application where this might happen because of excessive although
> logically correct recursion.  You have not given a single example where
> it actually happened.

I will. Stack overflow *can* happen with a bad base case. It *will* 
happen with correct linear recursion* applied to a large enough 
collection on a finite-memory machine (as opposed to an 'infinite' 
memory Turing machine).

def count_popable_collection(pop_col):
     try:
         pop_col.pop()
         return count_popable_collection(pop_col) + 1
     except (KeyError,IndexError):
         return 0

print(count_popable_collection({1,2,3}))
print(count_popable_collection([1,2,3]))

Both calls correctly print 3, but will fail for large enough sets or 
lists. I call the above body recursion*. A tail-recursive version

def count_popable_collection2(pop_col, cnt=0):
     try:
         pop_col.pop()
         return count_popable_collection2(pop_col, cnt + 1)
     except (KeyError,IndexError):
         return cnt

print(count_popable_collection2({1,2,3}))
print(count_popable_collection2([1,2,3]))

is less clear to most people, I think, and, executed as written, fails 
at the same point with the same memory error. Try either of the above 
with list(range(bignum)) (I am using 3.2).

This does not make linear recursion 'bad', just impractical for general 
use on finite-memory machines. While I consider it very useful for 
learning, it is unnecessary because it is easy to write an iterative 
version. So called tail-recursion optimization saves memory by REMOVING 
RECURSION and replacing it with iteration.

def count_popable_collection3(pop_col):
   cnt = 0
   while True:
     try:
         pop_col.pop()
         cnt += 1
     except (KeyError,IndexError):
         return cnt

print(count_popable_collection3({1,2,3}))
print(count_popable_collection3([1,2,3]))

Python does not do this automatically because 1) it can be a semantic 
change under some circumstances; 2) one who wants the iterative version 
can just as easily write it directly; and 3) Python has a better way to 
process collections that removes essentially all the boilerplate in the 
recursive-call and while-loop versions:

def count_popable_collection4(pop_col):
     cnt = 0
     for item in pop_col:
         cnt += 1
     return cnt

print(count_popable_collection4({1,2,3}))
print(count_popable_collection4([1,2,3]))


Binary recursion* is a different case because the exponential growth in 
leaf number and hence time limits the useful depth of recursion to well 
below the default of 1000.

* linear recursion: usually and at most one recursive call per call
* binary recursion: usually and at most two recursive calls per call
   Fib is the best known example.
* tail recursion: base cases return completed calculations
* body recursion: base cases return starting values, often constants

-- 

Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#4480

On Sun, 01 May 2011 18:24:30 -0400, Terry Reedy
  <tjreedy@udel.edu> wrote:
:  This does not make linear recursion 'bad', just impractical for general 
:  use on finite-memory machines. While I consider it very useful for 
:  learning, it is unnecessary because it is easy to write an iterative 
:  version. So called tail-recursion optimization saves memory by REMOVING 
:  RECURSION and replacing it with iteration.
: (...)
:  Python does not do this automatically because 1) it can be a semantic 
:  change under some circumstances; 2) one who wants the iterative version 
:  can just as easily write it directly;

That's the silliest argument I ever heard.  The programmer should write
the code the way he and application domain experts think, i.e. very
often recursively.  The compiler should generate code the way the CPU
thinks (most optimally), i.e. iteratively.

Of course, I am not saying that one should always model problems
recursively, and thus also not that one should implement them
recursively.  Just that when a model is agreed recursively between
the stakeholders, one should get a compiler to do the optimisation,
not a programmer.

I always thought of python as a step forward, in the way it allows 
direct expression of so many alternative modes of thinking (imperative,
functional, recursion, iterators, etc).  If what you say is python
philosophy, it is a step backward in requiring the programmer to
think more about low-level technical matters which even C has managed
to leave for the compiler.

:        and 3) Python has a better way to 
:  process collections that removes essentially all the boilerplate in the 
:  recursive-call and while-loop versions:


-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#4485

On Mon, 02 May 2011 14:14:20 +0100, Hans Georg Schaathun wrote:

> On Sun, 01 May 2011 18:24:30 -0400, Terry Reedy
>   <tjreedy@udel.edu> wrote:
> :  This does not make linear recursion 'bad', just impractical for
> general :  use on finite-memory machines. While I consider it very
> useful for :  learning, it is unnecessary because it is easy to write an
> iterative :  version. So called tail-recursion optimization saves memory
> by REMOVING :  RECURSION and replacing it with iteration. : (...)
> :  Python does not do this automatically because 1) it can be a semantic
> :  change under some circumstances; 2) one who wants the iterative
> version :  can just as easily write it directly;
> 
> That's the silliest argument I ever heard.

You must be new to the Internet then :)


> The programmer should write
> the code the way he and application domain experts think, i.e. very
> often recursively.  The compiler should generate code the way the CPU
> thinks (most optimally), i.e. iteratively.

Perhaps so, but there can be a huge gulf between what "should" happen and 
what does happen. The CPython implementation is deliberately a naive, not-
very clever compiler. (PyPy seems to be the implementation aiming at 
cutting-edge cleverness.)

Even such simple optimizations as constant folding are very controversial 
among the CPython developers. They have good reasons for their caution: 
optimizing compilers are renowned for breaking code, especially floating 
point code, and there have been cases in Python's history where 
optimizations have broken existing code and needed to be backed out.

The problem is, once you include side-effects, recursion and iteration 
are *not* identical. Specifically, the opposition to tail-recursion 
optimization in Python is that it plays havoc with the tracebacks you get 
in the event of an exception. The argument goes:

* Debugging is harder than writing code in the first place, so it is more 
important to simplify debugging, even at the cost of making some code 
slightly harder to write.

* Recursion doesn't just mean simple recursion where a function calls 
itself, but mutually recursive functions. You could have (say) five 
functions that mutually called each other recursively, and in the event 
of a traceback you need to see the exact calling chain, but that's 
precisely the information that is blown away by tail-recursion 
optimization.

* Tail-recursion is only a special case of recursion, and not a very 
common special case either, so it is hardly worth the extra complexity of 
the compiler to treat it specially.

Regardless of whether you agree with the arguments or not, they're hardly 
"silly".


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#4497

On 02 May 2011 16:41:37 GMT, Steven D'Aprano
  <steve+comp.lang.python@pearwood.info> wrote:
:  You must be new to the Internet then :)

OK.  Maybe I heard something worse last time I was an active news users,
years ago.

Anyway, most of the silly things I hear do not qualify as arguments :-)

:  The problem is, once you include side-effects, recursion and iteration 
:  are *not* identical. Specifically, the opposition to tail-recursion 
:  optimization in Python is that it plays havoc with the tracebacks you get 
:  in the event of an exception. The argument goes:

Thanks for the comprehensive background.  I can see the point that
python may be harder to optimise correctly during compilation than
many other languages.

:  Regardless of whether you agree with the arguments or not, they're hardly 
:  "silly".

I only called one argument silly, namely the one about iterative 
rewriting being so simple that it is not an issue.  Sometimes it isn't,
but sometimes it is.

The other arguments are valid.  And they make me lean more towards
more static, compiled languages without the excessive run-time 
dynamism of python.

-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#4510

On Mon, 02 May 2011 21:02:43 +0100, Hans Georg Schaathun wrote:

> The other arguments are valid.  And they make me lean more towards more
> static, compiled languages without the excessive run-time dynamism of
> python.

If you value runtime efficiency over development time, sure. There are 
plenty of languages which have made that decision: Pascal, C, Java, Lisp, 
Forth, and many more.

Python aims at acceptable performance (between 10 and 100 times slower 
than C) and much easier development (between 10 and 100 times faster than 
C *wink*). If that tradeoff doesn't suit you, perhaps Python is not the 
language for you.


-- 
Steven

[toc] | [prev] | [next] | [standalone]

#4518

On May 3, 5:21 am, Steven D'Aprano <steve
+comp.lang.pyt...@pearwood.info> wrote:
> On Mon, 02 May 2011 21:02:43 +0100, Hans Georg Schaathun wrote:
> > The other arguments are valid.  And they make me lean more towards more
> > static, compiled languages without the excessive run-time dynamism of
> > python.
>
> If you value runtime efficiency over development time, sure. There are
> plenty of languages which have made that decision: Pascal, C, Java, Lisp,
> Forth, and many more.

Or Haskell:

Succinctness like python
Type safety better than C, C++, Java with a minimum of type
declarations

[toc] | [prev] | [next] | [standalone]

#4527

On 03 May 2011 00:21:45 GMT, Steven D'Aprano
  <steve+comp.lang.python@pearwood.info> wrote:
:  Python aims at acceptable performance (between 10 and 100 times slower 
:  than C) and much easier development (between 10 and 100 times faster than 
:  C *wink*). If that tradeoff doesn't suit you, perhaps Python is not the 
:  language for you.

It isn't the trade-off per se which bothers me, but certain features
which seem to make compilation harder without making development any
easier.  

But then, it probably depeds on what kind of development you are doing.

-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web