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

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

English Idiom in Unix: Directory Recursively

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

Contents

  English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-17 15:26 -0700
    Re: English Idiom in Unix: Directory Recursively Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-17 17:20 -0600
      Re: English Idiom in Unix: Directory Recursively "Martin P. Hellwig" <martin.hellwig@gmail.com> - 2011-05-18 22:22 +0000
    Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-18 09:42 +1000
    Re: English Idiom in Unix: Directory Recursively "Steven W. Orr" <steveo@syslang.net> - 2011-05-17 21:16 -0400
    Re: English Idiom in Unix: Directory Recursively Roland Hutchinson <my.spamtrap@verizon.net> - 2011-05-18 04:51 +0000
      Re: English Idiom in Unix: Directory Recursively "Pascal J. Bourguignon" <pjb@informatimago.com> - 2011-05-18 07:19 +0200
        Re: English Idiom in Unix: Directory Recursively tar@sevak.isi.edu (Thomas A. Russ) - 2011-05-17 23:42 -0700
          Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 09:26 +0100
            Re: English Idiom in Unix: Directory Recursively tar@sevak.isi.edu (Thomas A. Russ) - 2011-05-18 09:16 -0700
              Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 19:11 +0100
                Re: English Idiom in Unix: Directory Recursively Raymond Wiker <raw@RAWMBP-2.local> - 2011-05-18 20:20 +0200
                  Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 19:39 +0100
                    Re: English Idiom in Unix: Directory Recursively Raymond Wiker <raw@RAWMBP-2.local> - 2011-05-18 21:09 +0200
                      Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 21:02 +0100
                        Re: English Idiom in Unix: Directory Recursively Raymond Wiker <raw@RAWMBP-2.local> - 2011-05-18 22:40 +0200
                          Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-19 05:56 +0100
                    Re: English Idiom in Unix: Directory Recursively tar@sevak.isi.edu (Thomas A. Russ) - 2011-05-19 16:14 -0700
                  Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-19 04:41 +1000
              Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-19 04:12 +1000
              Re: English Idiom in Unix: Directory Recursively "Pascal J. Bourguignon" <pjb@informatimago.com> - 2011-05-18 20:57 +0200
                Re: English Idiom in Unix: Directory Recursively tar@sevak.isi.edu (Thomas A. Russ) - 2011-05-19 16:17 -0700
                  Re: English Idiom in Unix: Directory Recursively "Pascal J. Bourguignon" <pjb@informatimago.com> - 2011-05-20 02:38 +0200
                    Re: English Idiom in Unix: Directory Recursively Antti J Ylikoski <antti.ylikoski@tkk.fi> - 2011-05-20 12:00 +0300
          Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-18 22:09 +1000
            Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-18 06:14 -0700
              Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-19 11:06 +1000
                Re: English Idiom in Unix: Directory Recursively Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-21 09:32 +0100
                  Re: English Idiom in Unix: Directory Recursively Lars Enderin <lars.enderin@telia.com> - 2011-05-21 11:52 +0200
                    Re: English Idiom in Unix: Directory Recursively Lars Enderin <lars.enderin@telia.com> - 2011-05-21 11:54 +0200
                      Re: English Idiom in Unix: Directory Recursively Lars Enderin <lars.enderin@telia.com> - 2011-05-21 11:56 +0200
                Re: English Idiom in Unix: Directory Recursively Grant Edwards <invalid@invalid.invalid> - 2011-05-21 15:34 +0000
        Re: English Idiom in Unix: Directory Recursively Roland Hutchinson <my.spamtrap@verizon.net> - 2011-05-20 06:50 +0000
      Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-17 23:06 -0700
        Re: English Idiom in Unix: Directory Recursively Harrison Hill <harrishill@gmx.com> - 2011-05-17 23:50 -0700
          Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-18 00:16 -0700
          Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-18 22:19 +1000
            Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:16 -0700
              Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-30 22:58 +1000
          Re: English Idiom in Unix: Directory Recursively see@sig.for.address (Victor Eijkhout) - 2011-05-18 12:59 -0500
            Re: English Idiom in Unix: Directory Recursively Roland Hutchinson <my.spamtrap@verizon.net> - 2011-05-20 06:54 +0000
              Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-20 17:10 +1000
            Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:28 -0700
              Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-30 23:02 +1000
            Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:28 -0700
          Re: English Idiom in Unix: Directory Recursively Glenn Knickerbocker <NotR@bestweb.net> - 2011-05-18 16:54 -0400
        Re: English Idiom in Unix: Directory Recursively Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-18 00:58 -0600
          Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-18 00:10 -0700
            Re: English Idiom in Unix: Directory Recursively Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-18 08:32 -0600
              Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-18 08:15 -0700
                Re: English Idiom in Unix: Directory Recursively Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-18 09:43 -0600
    Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 09:12 +0100
      Re: English Idiom in Unix: Directory Recursively Espen Vestre <espen@vestre.net> - 2011-05-18 10:20 +0200
      Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-19 23:21 +0200
        Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-20 05:28 +0100
          Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-23 20:48 +0200
        Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-19 22:13 -0700
          Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-20 06:55 +0000
            Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-20 09:48 +0100
              Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-20 10:21 -0700
            Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-23 20:56 +0200
              Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-24 00:18 +0000
                Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-25 00:06 +0200
                  Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-25 10:40 +1000
                    Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 14:18 -0700
                    Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 14:19 -0700
                  Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-24 23:05 -0700
                  Re: English Idiom in Unix: Directory Recursively Thorsten Kampe <thorsten@thorstenkampe.de> - 2011-05-25 09:26 +0200
                    Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-25 00:51 -0700
                      Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-25 17:59 +1000
                    Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-25 21:59 +0000
                      Re: English Idiom in Unix: Directory Recursively Thorsten Kampe <thorsten@thorstenkampe.de> - 2011-05-26 10:48 +0200
                        Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-26 10:06 +0000
                          Re: English Idiom in Unix: Directory Recursively Thorsten Kampe <thorsten@thorstenkampe.de> - 2011-05-26 12:46 +0200
                      Re: English Idiom in Unix: Directory Recursively harrismh777 <harrismh777@charter.net> - 2011-05-27 09:31 -0500
                  Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-25 22:58 +0000
                    Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-26 14:00 +1000
                    Re: English Idiom in Unix: Directory Recursively Thorsten Kampe <thorsten@thorstenkampe.de> - 2011-05-26 10:59 +0200
                      Re: English Idiom in Unix: Directory Recursively "Charles" <C.Sanders@DeleteThis.Bom.GOV.AU> - 2011-05-26 20:58 +1000
                        Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-26 21:12 +1000
                          Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 14:38 -0700
                            Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-30 07:46 +1000
                              Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 15:54 -0700
                          Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 14:38 -0700
                        Re: English Idiom in Unix: Directory Recursively Thorsten Kampe <thorsten@thorstenkampe.de> - 2011-05-26 13:20 +0200
                          Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-26 21:28 +1000
                          Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-26 14:51 -0700
                    Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-28 21:36 +0200
                      Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-29 05:58 +1000
                        Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-29 00:49 +0000
                        Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-30 23:04 +0200
                          Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-30 23:17 +0000
                      Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-29 07:28 +1000
                        Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-30 23:10 +0200
                  Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:58 -0700
                    Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-30 07:27 +1000
            Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:39 -0700
    Re: English Idiom in Unix: Directory Recursively Mike Barnes <mikebarnes@bluebottle.com> - 2011-05-18 10:25 +0100
      Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-18 13:00 -0700
        Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 21:19 +0100
          Re: English Idiom in Unix: Directory Recursively Lanarcam <lanarcam1@yahoo.fr> - 2011-05-18 22:33 +0200
        Re: English Idiom in Unix: Directory Recursively Mike Barnes <mikebarnes@bluebottle.com> - 2011-05-18 22:00 +0100
        Re: English Idiom in Unix: Directory Recursively Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-20 08:10 +0100
          Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-22 13:22 -0700
            Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-23 08:46 +1000
              Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-22 16:17 -0700
                Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-23 09:32 +1000
                  Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-23 21:20 -0700
                    Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-24 14:28 +1000
                      Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-24 10:40 -0700
                        Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-25 08:14 +1000
                          Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-25 10:15 +0000
        Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:32 -0700
      Re: English Idiom in Unix: Directory Recursively Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-20 08:07 +0100
    Re: English Idiom in Unix: Directory Recursively John Nagle <nagle@animats.com> - 2011-05-18 13:07 -0700
    Re: English Idiom in Unix: Directory Recursively Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-20 08:00 +0100
      Re: English Idiom in Unix: Directory Recursively David Schwartz <davids@webmaster.com> - 2011-05-27 22:56 -0700

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6  Next page →

#5727

tar@sevak.isi.edu (Thomas A. Russ) writes:

> Well, unless you have a tree with backpointers, you have to keep the
> entire parent chain of nodes visited.  Otherwise, you won't be able to
> find the parent node when you need to backtrack.  A standard tree
> representation has only directional links.
>
> Consider:
>
> A--+---B----+---D
>    |        |
>    |        +---E
>    |        |
>    |        +---F
>    | 
>    +---C
>
> If all you keep is the current and previous node, then the only thing
> you have reference do when doing the depth-first traverse is:
>   1.  Current = A,  Previous = null
>   2.  Current = B.  Previous = A
>   3.  Current = D   Previous = B
>   4.  Current = E   Previous = D
>   5.  now what?  You can't get from E or D back to B.
>
>> By comparing the previous node (pointer or ID) to the
>> current node's parent and children one will know wherefrom the
>> current node was entered, and can choose the next child in the
>> list as the next node, or the parent if all children have been
>> visited.  A visit action may be added in any or all times the
>> node is visited.
>> 
>> This node requires no stack.  The only state space is constant,
>> regardless of the size of the tree, requiring just the two pointers
>> to previous and current.
>
> This will only work if there is a backpointer to the parent.

No, you don't need backpointers; some cases have been mentionned in the
other answer, but in general:

    (defun parent (tree node)
       (if (member node (children tree))
          tree
          (some (lambda (child) (parent child node)) (children tree))))

Yes, the question wasn't about time complexity.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

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

#5797

"Pascal J. Bourguignon" <pjb@informatimago.com> writes:

> tar@sevak.isi.edu (Thomas A. Russ) writes:
> >
> > This will only work if there is a backpointer to the parent.
> 
> No, you don't need backpointers; some cases have been mentionned in the
> other answer, but in general:
> 
>     (defun parent (tree node)
>        (if (member node (children tree))
>           tree
>           (some (lambda (child) (parent child node)) (children tree))))
> 
> Yes, the question wasn't about time complexity.

 :-p

Um, this is a recursive function.  Inside PARENT, there is another call
to PARENT.

-- 
Thomas A. Russ,  USC/Information Sciences Institute

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

#5799

tar@sevak.isi.edu (Thomas A. Russ) writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
>
>> tar@sevak.isi.edu (Thomas A. Russ) writes:
>> >
>> > This will only work if there is a backpointer to the parent.
>> 
>> No, you don't need backpointers; some cases have been mentionned in the
>> other answer, but in general:
>> 
>>     (defun parent (tree node)
>>        (if (member node (children tree))
>>           tree
>>           (some (lambda (child) (parent child node)) (children tree))))
>> 
>> Yes, the question wasn't about time complexity.
>
>  :-p
>
> Um, this is a recursive function.  Inside PARENT, there is another call
> to PARENT.

Feel free to derecursive it.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

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

#5843

On 20.5.2011 3:38, Pascal J. Bourguignon wrote:
> tar@sevak.isi.edu (Thomas A. Russ) writes:
>
>> "Pascal J. Bourguignon"<pjb@informatimago.com>  writes:
>>
>>> tar@sevak.isi.edu (Thomas A. Russ) writes:
>>>>
>>>> This will only work if there is a backpointer to the parent.
>>>
>>> No, you don't need backpointers; some cases have been mentionned in the
>>> other answer, but in general:
>>>
>>>      (defun parent (tree node)
>>>         (if (member node (children tree))
>>>            tree
>>>            (some (lambda (child) (parent child node)) (children tree))))
>>>
>>> Yes, the question wasn't about time complexity.
>>
>>   :-p
>>
>> Um, this is a recursive function.  Inside PARENT, there is another call
>> to PARENT.
>
> Feel free to derecursive it.
>

In the general case, to derecursive a function necessitates programming 
a stack, among other things.............

Antti "Andy" Ylikoski

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

#5681

Thomas A. Russ wrote:
> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
> 
>> Roland Hutchinson <my.spamtrap@verizon.net> writes:
> 
>>> Tail recursion  can always be turned into an iteration when it is
>>> executed.  
>> All recursions can be turned into iterations, before execution.
> 
> True, but only by simulating the call stack in the iterative code.  To
> my mind that isn't really an iterative algorithm anymore if it ends up
> simulating the call stack.

When does a data structure stop being a simulation of a stack?  I've
often had to turn recursive algorithms into iterative ones, where the
solution turned out to be "simulating the call stack" only in a very
broad sense; a big stretch of the imagination is needed to see the
equivalent of push or pop operations.

> Tree walks are the canonical example of what can't be done in an
> iterative fashion without the addition of an explicitly managed stack

Let me throw in an example where the desired tree walk is neither
depth-first or breadth-first.  It's to do with the way I display my
family tree on my web site; an example may be found at
   http://www.pmoylan.org/cgi-bin/wft.cmd?D=moylan;P=I004
Most people familiar with algorithm design will, I believe, end up
deciding that the appropriate data structure in this case is a queue
rather than a stack.

ObAUE: In common parlance, the English word "recursion" means pretty
much the same as what computing people call "iteration".  This might be
the first time I have ever found a point of agreement with Xah Lee.

-- 
Peter Moylan, Newcastle, NSW, Australia.      http://www.pmoylan.org
For an e-mail address, see my web page.

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

#5691

On May 18, 5:09 pm, Peter Moylan <inva...@peter.pmoylan.org.invalid>
wrote:
>
> ObAUE: In common parlance, the English word "recursion" means pretty
> much the same as what computing people call "iteration".  This might be
> the first time I have ever found a point of agreement with Xah Lee.

Maybe the common usage mirrors the facts better than the lore that
half-baked programmers remain devoted to. Consider first
implementations:

The implementation of recursion by a typical language (eg gcc for C)
maximizes generality at the cost of efficiency

The implementation of a very special case -- tail recursion -- in some
special languages (most notably scheme) is required to be competitive
with the iterative solution.

[If I remember right in Chez scheme tail recursion was more efficient
than a do (iteration) because a do typically needed assignment and
assignment was more expensive than parameter passing]

But there is a wide spectrum of cases between the most general case of
recursion and tail recursion.

Some examples
1 A non-tail recursive function, with a single recursive call, when
implemented naively would push the return address.  This is
unnecessary as only a flag needs to be pushed -- return to internal
call point or return to external call point.  This itself can be
efficiently simulated by storing the recursion depth -- zero => jump
out; > 0 => jump to internal call

2. A single function with double recursion -- quicksort is the classic
-- can be implemented without recursion or stack.  It just needs a set
of pending begin-end pairs yet to be sorted.
This may look like the stack in another guise but unlike the stack it
does not need to store any function call return paraphernalia.

3. Tree recursion (though not the case of the OP) can be solved non-
recursively with threading
http://en.wikipedia.org/wiki/Threaded_binary_tree
and Schorr Waite Deutsch
http://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec21-schorr-waite.pdf

In fact the only example I can think of where the full blown
generality of recursion cannot be tightened is perhaps recursive
descent parsing.

So much for implementations.

Semantically the while loop

while B:
  statement

is equivalent to the recursion:

def stateiter():
  if B:
     statement
     stateiter()

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

#5757

rusi wrote:
> On May 18, 5:09 pm, Peter Moylan <inva...@peter.pmoylan.org.invalid>
> wrote:
>> ObAUE: In common parlance, the English word "recursion" means pretty
>> much the same as what computing people call "iteration".  This might be
>> the first time I have ever found a point of agreement with Xah Lee.
> 
> Maybe the common usage mirrors the facts better than the lore that
> half-baked programmers remain devoted to. Consider first
> implementations:
> 
> The implementation of recursion by a typical language (eg gcc for C)
> maximizes generality at the cost of efficiency
> 
> The implementation of a very special case -- tail recursion -- in some
> special languages (most notably scheme) is required to be competitive
> with the iterative solution.
> 
> [If I remember right in Chez scheme tail recursion was more efficient
> than a do (iteration) because a do typically needed assignment and
> assignment was more expensive than parameter passing]

I believe the word "legend", or something equivalent, was used elsewhere
in this thread in this connection.  The supposed inefficiency of
recursive implementations is based largely on the properties of hardware
that is now obsolete.  With modern processors there's no great
efficiency hit.  In some of the smaller microcontrollers, it's true, you
do have to worry about stack overflow; but the ARM processors, for
example, provide plenty of stack space.

In the microcontroller world, the big performance hits come from the
fact that the only available compilers are for C and sometimes C++.
(And nobody uses assembly language except for the very little jobs.)
The nature of the C language prevents compilers from doing optimisations
that are standard in compilers for high-level languages.  Most C
compilers will, for example, always pass parameters on the stack,
despite the generous supply of registers available in newer hardware.

-- 
Peter Moylan, Newcastle, NSW, Australia.      http://www.pmoylan.org
For an e-mail address, see my web page.

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

#5910

> The supposed inefficiency of recursive implementations is based 
> largely on the properties of hardware that is now obsolete. With 
> modern processors there's no great efficiency hit. In some of the 
> smaller microcontrollers, it's true, you do have to worry about stack 
> overflow; but the ARM processors, for example, provide plenty of stack 
> space.
>
> In the microcontroller world, the big performance hits come from the 
> fact that the only available compilers are for C and sometimes C++. 
> (And nobody uses assembly language except for the very little jobs.) 
> The nature of the C language prevents compilers from doing 
> optimisations that are standard in compilers for high-level languages. 
> Most C compilers will, for example, always pass parameters on the 
> stack, despite the generous supply of registers available in newer 
> hardware.
>
However, some C compilers will *also* have one or more "go faster" 
calling conventions that pass parameters in registers, which can be 
employed.  Over in the PC world, such "go faster" calling conventions 
are even the default calling convention if no calling convention is 
explicitly specified, for some C and C++ compilers.

     
http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Compiler
     
http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Optlink
     
http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Watcall

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

#5912

2011-05-21 10:32, Jonathan de Boyne Pollard skrev:
>> The supposed inefficiency of recursive implementations is based
>> largely on the properties of hardware that is now obsolete. With
>> modern processors there's no great efficiency hit. In some of the
>> smaller microcontrollers, it's true, you do have to worry about stack
>> overflow; but the ARM processors, for example, provide plenty of stack
>> space.
>>
>> In the microcontroller world, the big performance hits come from the
>> fact that the only available compilers are for C and sometimes C++.
>> (And nobody uses assembly language except for the very little jobs.)
>> The nature of the C language prevents compilers from doing
>> optimisations that are standard in compilers for high-level languages.
>> Most C compilers will, for example, always pass parameters on the
>> stack, despite the generous supply of registers available in newer
>> hardware.
>>
> However, some C compilers will *also* have one or more "go faster"
> calling conventions that pass parameters in registers, which can be
> employed.  Over in the PC world, such "go faster" calling conventions
> are even the default calling convention if no calling convention is
> explicitly specified, for some C and C++ compilers.
> 
>    
> http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Compiler
> 
>    
> http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Optlink
> 
>    
> http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Watcall
> 

Please include attributions, in this case for Peter Moylan and rusi!

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

#5913

2011-05-21 11:52, Lars Enderin skrev:
> 
> Please include attributions, in this case for Peter Moylan and rusi!

Just Peter Moylan, sorry!

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

#5914

2011-05-21 11:54, Lars Enderin skrev:
> 2011-05-21 11:52, Lars Enderin skrev:
>>
>> Please include attributions, in this case for Peter Moylan and rusi!
> 
> Just Peter Moylan, sorry!

Ignore the above.

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

#5925

On 2011-05-19, Peter Moylan <invalid@peter.pmoylan.org.invalid> wrote:

> In the microcontroller world, the big performance hits come from the
> fact that the only available compilers are for C and sometimes C++.
> (And nobody uses assembly language except for the very little jobs.)
> The nature of the C language prevents compilers from doing optimisations
> that are standard in compilers for high-level languages.  Most C
> compilers will, for example, always pass parameters on the stack,
> despite the generous supply of registers available in newer hardware.

I've been doing microcontroller stuff for 25+ years, almost all in C,
and I don't think I've never seen such a compiler.  Even on the
register-starved 6800 architecture, the first parameter was passed in
a register.  On architectures with more registers (H8, MSP430, ARM,
etc.) It's usually the first 3 or so parameters that are found in
registers.

-- 
Grant Edwards               grant.b.edwards        Yow! Gee, I feel kind of
                                  at               LIGHT in the head now,
                              gmail.com            knowing I can't make my
                                                   satellite dish PAYMENTS!

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

#5823

On Wed, 18 May 2011 07:19:08 +0200, Pascal J. Bourguignon wrote:

> Roland Hutchinson <my.spamtrap@verizon.net> writes:
> 
>> Sorry to have to contradict you,
> 
> Don't be sorry.
> 
> 
>> but it really is a textbook example of recursion.  Try this psuedo-code
>> on for size:
>>
>> FUNCTION DIR-DELETE (directory)
>>   FOR EACH entry IN directory
>>   IF entry IS-A-DIRECTORY THEN DIR-DELETE (entry).
>>
>> Well, now that's not just recursion; it's tail recursion.
> 
> It's not tail recursion.  If you had indented your code properly, you'd
> see why it's not:
> 
>     (defun dir-delete (directory)
>       (loop for entry in directory
>             do (if (is-a-directory entry)
>                    (dir-delete entry))))
> 

You are right, of course.  Thanks for the correction.

> (I put parentheses, so my editor knows what I mean and can do the
> indentation for me).

My editor would have done that, too--if I had bothered to be thinking 
clearly.

> That's why walking a directory is done with a recursive procedure,
> instead of an iterative one: it's much simplier.  To implement an
> iterative procedure, you would have to manage a stack yourself, instead
> of using the implicit stack of the recursive procedure.

Got it!  Thanks again.


-- 
Roland Hutchinson		

He calls himself "the Garden State's leading violist da gamba,"
... comparable to being ruler of an exceptionally small duchy.
--Newark (NJ) Star Ledger  ( http://tinyurl.com/RolandIsNJ ) 

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

#5657

On May 18, 9:51 am, Roland Hutchinson <my.spamt...@verizon.net> wrote:

> Sorry to have to contradict you, but it really is a textbook example of
> recursion.  Try this psuedo-code on for size:  

Well and so far this thread is a textbook example of myths and
misconceptions regarding recursion :D

1. 'Recursive' is a meaningful adjective for algorithms only and not
data structures

2. Recursion is inefficient

which is a corollary to

3. Recursion is different from (more general, less efficient)
iteration

4. Recursion in 'recursion theory' aka 'computability theory' is
somehow different from recursion in programming.

Let me start with 1.

The Haskell (pseudocode) defn for lists is:
   data List(t) = []    |    (:) t List(t)

In words, a list over type t is either empty or is made byt taking a
(smaller) list and consing (:) and element onto it

It is only given this defn that al the list functions which are (in
the sense that
most programmers understand) recursive. For example:

len [] = 0
len (x:xs) = 1 + len xs

Note that the definition of List is primary and the recursive
functions on this definition are secondary to this definition.

What happens in languages more and more far from the 'functional
purity' of Haskell?
Much the same except that implementation details muddy the waters.

eg in C the defn for list (of an elsewhere specified type t) runs thus

struct node {
  t elem;
  struct node *next;
}


To make the recursion more explicit, introduce the typedef:

typedef struct node *nodeptr;

struct node {
  t elem;
  nodeptr next;
};

And we see clearly a mutual recursion in this data type:
node contains nodeptr
nodeptr points to node

So one could say that the C defn is more recursive than the Haskell
one in the sense that double recursion is 'more recursion' than
single.

I could continue down 2,3,4 but really it may be worthwhile if the
arguers first read the wikipedia disambiguation pages on recursion...

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

#5661

On May 18, 7:06 am, rusi <rustompm...@gmail.com> wrote:
> On May 18, 9:51 am, Roland Hutchinson <my.spamt...@verizon.net> wrote:
>
> > Sorry to have to contradict you, but it really is a textbook example of
> > recursion.  Try this psuedo-code on for size:  
>
> Well and so far this thread is a textbook example of myths and
> misconceptions regarding recursion :D
>
> 1. 'Recursive' is a meaningful adjective for algorithms only and not
> data structures
>
> 2. Recursion is inefficient
>
> which is a corollary to
>
> 3. Recursion is different from (more general, less efficient)
> iteration
>
> 4. Recursion in 'recursion theory' aka 'computability theory' is
> somehow different from recursion in programming.
>
> Let me start with 1.
>
> The Haskell (pseudocode) defn for lists is:
>    data List(t) = []    |    (:) t List(t)
>
> In words, a list over type t is either empty or is made byt taking a
> (smaller) list and consing (:) and element onto it
>
> It is only given this defn that al the list functions which are (in
> the sense that
> most programmers understand) recursive. For example:
>
> len [] = 0
> len (x:xs) = 1 + len xs
>
> Note that the definition of List is primary and the recursive
> functions on this definition are secondary to this definition.
>
> What happens in languages more and more far from the 'functional
> purity' of Haskell?
> Much the same except that implementation details muddy the waters.
>
> eg in C the defn for list (of an elsewhere specified type t) runs thus
>
> struct node {
>   t elem;
>   struct node *next;
>
> }
>
> To make the recursion more explicit, introduce the typedef:
>
> typedef struct node *nodeptr;
>
> struct node {
>   t elem;
>   nodeptr next;
>
> };
>
> And we see clearly a mutual recursion in this data type:
> node contains nodeptr
> nodeptr points to node
>
> So one could say that the C defn is more recursive than the Haskell
> one in the sense that double recursion is 'more recursion' than
> single.
>
> I could continue down 2,3,4 but really it may be worthwhile if the
> arguers first read the wikipedia disambiguation pages on recursion...

No need - I have the Dictionary definition of recursion here:

Recursion: (N). See recursion.

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

#5667

On May 18, 11:50 am, Harrison Hill <harrish...@gmx.com> wrote:
> Rusi wrote
> > I could continue down 2,3,4 but really it may be worthwhile if the
> > arguers first read the wikipedia disambiguation pages on recursion...
>
> No need - I have the Dictionary definition of recursion here:
>
> Recursion: (N). See recursion.

Ha! Ha!

Worth also looking at the talk page of the recursive disambiguation
page:

http://en.wikipedia.org/wiki/Talk:Recursive

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

#5682

Harrison Hill wrote:
> On May 18, 7:06 am, rusi <rustompm...@gmail.com> wrote:

>> I could continue down 2,3,4 but really it may be worthwhile if the
>> arguers first read the wikipedia disambiguation pages on recursion...
> 
> No need - I have the Dictionary definition of recursion here:
> 
> Recursion: (N). See recursion.

It's interesting to note that the definitions of 'recursive' to be found
in Wikipedia and Wiktionary have very little in common with the
definitions to be found in the dictionaries covered by Onelook.  No
wonder experts in different areas have trouble communicating with one
another.

-- 
Peter Moylan, Newcastle, NSW, Australia.      http://www.pmoylan.org
For an e-mail address, see my web page.

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

#6568

On May 18, 7:19 am, Peter Moylan <inva...@peter.pmoylan.org.invalid>
wrote:

> It's interesting to note that the definitions of 'recursive' to be found
> in Wikipedia and Wiktionary have very little in common with the
> definitions to be found in the dictionaries covered by Onelook.  No
> wonder experts in different areas have trouble communicating with one
> another.

Yes, and when you extrapolate that conclusion into the current hodge
podge of natural languages you begin to understand the genesis of
human beings selfish nature.

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

#6654

rantingrick wrote:
> On May 18, 7:19 am, Peter Moylan <inva...@peter.pmoylan.org.invalid>
> wrote:
> 
>> It's interesting to note that the definitions of 'recursive' to be found
>> in Wikipedia and Wiktionary have very little in common with the
>> definitions to be found in the dictionaries covered by Onelook.  No
>> wonder experts in different areas have trouble communicating with one
>> another.
> 
> Yes, and when you extrapolate that conclusion into the current hodge
> podge of natural languages you begin to understand the genesis of
> human beings selfish nature.

I do?

-- 
Peter Moylan, Newcastle, NSW, Australia.      http://www.pmoylan.org
For an e-mail address, see my web page.

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

#5715

Harrison Hill <harrishill@gmx.com> wrote:

> No need - I have the Dictionary definition of recursion here:
> 
> Recursion: (N). See recursion.

If you tell a joke, you have to tell it right.

Recursion: (N). See recursion. See also tail recursion.

Victor.
-- 
Victor Eijkhout -- eijkhout at tacc utexas edu

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

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6  Next page →

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

csiph-web