Profiling, recursive func slower than imperative, normal?

[MRAB]

On Apr 17, 9:39 am, Robert Bossy <Robert.Bo... at jouy.inra.fr> wrote:
> Gabriel Genellina wrote:
> > En Wed, 16 Apr 2008 17:53:16 -0300, <s0s... at gmail.com> escribió:
>
> >> On Apr 16, 3:27 pm, Jean-Paul Calderone <exar... at divmod.com> wrote:
>
> >>> Any function can be implemented without recursion, although it isn't
> >>> always easy or fun.
>
> >> Really? I'm curious about that, I can't figure out how that would
> >> work. Could give an example? Say, for example, the typical: walking
> >> through the file system hierarchy (without using os.walk(), which uses
> >> recursion anyway!).
>
> > Use a queue of pending directories to visit:
>
> > start with empty queue
> > queue.put(starting dir)
> > while queue is not empty:
> >    dir = queue.get()
> >    list names in dir
> >    for each name:
> >      if is subdirectory: queue.put(name)
> >      else: process file
>
> Hi,
>
> In that case, I'm not sure you get any performance gain since the queue
> has basically the same role as the stack in the recursive version. A
> definitive answer calls for an actual test, though.
>
> Anyway if you want to process the tree depth-first, the queue version
> falls in the "not fun" category.
>
If you store the folders in a queue (push onto one end and pop from
the other end) the search is breadth-first; if you store the folders
in a stack (push onto one end and pop from the same end) the search is
depth-first. Simple really! :-)