CODEWITHSUNDEEP
pythonrecursion
David542
David542

Reputation: 110113

Non recursive way to list files

I have the following to recursively list files in a directory:

import os

def listdir(dir):
    items = [dir + '/' + item for item in os.listdir(dir)]
    for item in items:
        if not os.path.isdir(item):
            print (item)
        else:
            listdir(item)

As a sort of academic exercise I wanted to see how the above could be converted into a loop without recursion. What would be an example of doing that? So far I had something along the lines of:

def listdir(dir):
    while True:
        items = os.listdir(dir)
        for item in items:
            if not is.path.isdir(item):
                print (item)
            else:
                 # ?

Upvotes: 2

Views: 1055

Answers (4)

xjcl
xjcl

Reputation: 15309

You could use a FIFO queue (or equivalently, a deque):

def listdir(dir_initial):
    q = queue.Queue()
    q.put(dir_initial)

    while not q.empty():
        dir = q.get()
        items = os.listdir(dir)
        for item in items:
            item = dir + '/' + item
            if os.path.isdir(item):
                q.put(item)
            else:
                print(item)

If we encounter a directory we add it to the queue for later processing. If the queue is empty we know that we are done.

Note that this implements breadth-first search as opposed to the recursive depth-first search, meaning you will get:

/a/
/b/
/a/1/
/a/2/
/b/9/

instead of

/a/
/a/1/
/a/2/
/b/
/b/9/

Upvotes: 6

David542
David542

Reputation: 110113

Here's an example using a stack:

def listdir(dir):
    stack = [dir,]
    while stack:
        parent_dir = stack[-1]
        items = [parent_dir + '/' + item for item in os.listdir(stack.pop())]
        for item in items:
            if not os.path.isdir(item):
                print (item)
            else:
                stack.append(item)

Upvotes: 0

nbk
nbk

Reputation: 49373

Ok, after reconsidering, you can add the directiry to a list and process them

But your original code has some bugs and will not work

import os
def listdir(dir):
    dirstoprocess = []
    while True:
        items = os.listdir(dir)
        for item in items:
            if os.path.isfile(os.path.join(dir, item)):
                print (item)
            else:
                dirstoprocess.append(os.path.join(dir, item))
        
        if len(dirstoprocess) > 0:
            dir = dirstoprocess.pop(0)
        else:
            break
listdir("D:\mydi")

Upvotes: 0

Tytrox
Tytrox

Reputation: 538

You could build a 'stack' of directories to list, and every time you encounter a new directory, add it to the stack. You could then loop while the stack is not empty over all directories:

Upvotes: 1

Related Questions