Results 1 to 18 of 18

Thread: Avoiding recursion at all costs?

  1. #1

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Avoiding recursion at all costs?

    For once a question from me

    I'm writing a file search algorithm that searches every physical fixed drive and every network drive including all subdirectories for a filename. Although there is a shell function that brings up the file search box of Explorer, there seems to be no function to do this programmatically, neither in the shell nor in the file I/O functions.

    The problem I have is: the function that searches the directory tree could either be recursive (shiver) or use some kind of loop and an array to simulate the recursion.
    The tree-nature of directories requires two loops: one that walks into the depth of the tree and another that walks the directory siblings. The sibling-walker is the inner loop. The problem is that I can't use continue or break (or something like that) from within the inner loop to act on the outer loop. As I don't want to have cryptic continue flags the only way that seems left to me is using goto (*shiver again*).
    Here's my code (MFC, but a lot of API access).
    CList is a templated linked list. CStringList is equivalent to a specialization of CList for CString.
    CFileFind is a class that encapsulates the API WIN32_FIND_DATA, FindFirstFile and FindNextFile.
    Code:
    bool CJBStarterApp::SearchTree(const CString & strInitDir,
    	const CString & strFilename, CString & strOut)
    {
    	// Uses a freaky goto to avoid recursiveness.
    	// Makes you wonder...
    	CStringList lsStack;
    	CList<CFileFind *, CFileFind *> lpffStack;
    	CFileFind *pCurrentFF = NULL;
    	CString strCurDir(strInitDir);
    recur:
    	pCurrentFF = new CFileFind();
    	::SetCurrentDirectory(strCurDir);
    	if(pCurrentFF->FindFile(strFilename))
    	{
    		pCurrentFF->FindNextFile();
    		strOut = pCurrentFF->GetFilePath();
    		// Unroll stack and return
    		delete pCurrentFF;
    		while(!lpffStack.IsEmpty())
    			delete lpffStack.RemoveHead();
    		return true;
    	}
    	pCurrentFF->FindFile();
    	while(pCurrentFF->FindNextFile())
    	{
    		if(pCurrentFF->IsDirectory())
    		{
    			lpffStack.AddHead(pCurrentFF);
    			lsStack.AddHead(strCurDir);
    			strCurDir = pCurrentFF->GetFilePath();
    			goto recur;
    cont:
    			delete pCurrentFF;
    			pCurrentFF = lpffStack.RemoveHead();
    			strCurDir = lsStack.RemoveHead();
    			::SetCurrentDirectory(strCurDir);
    		}
    	}
    	if(lpffStack.IsEmpty())
    		return false;
    	goto cont;
    }
    I believe it should work (haven't tried yet), but I'm not sure and that's a bad sign. If I'm not able to follow program flow right after I've written the app then this can't be good.

    I welcome any ideas on restructuring this code to make it more readable. I welcome any reference to an API function that does this even more.

    Thanks in advance.
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  2. #2
    Hyperactive Member made_of_asp's Avatar
    Join Date
    Jul 2001
    Location
    123 Fake Street
    Posts
    394
    I always use recursion for directory tree search. Why do you want to avoid it?
    VS.NET 2003

    Need to email me?

  3. #3
    Hyperactive Member Cmdr0Sunburn's Avatar
    Join Date
    May 2001
    Location
    g0t r00t?
    Posts
    461
    im actually working on a file 'search' algo if you need to look at my code for examples(non mfc heh), ask, ill post it, it searches for all driev letters and loops(recursion) through them.
    I know a lot oF Vb, expert in C++, and i think in assembly.
    MSVC++6.NET
    vb6
    masm
    Windowz Xp
    I find my self using this a lot in C++

    __asm {
    }

  4. #4
    Good Ol' Platypus Sastraxi's Avatar
    Join Date
    Jan 2000
    Location
    Ontario, Canada
    Posts
    5,134
    Recursion puts a function on the stack, exiting that function pops it off. So, in low-memory environments, being several hundred functions deep can make you run out of stack space.
    All contents of the above post that aren't somebody elses are mine, not the property of some media corporation.
    (Just a heads-up)

  5. #5
    Hyperactive Member Cmdr0Sunburn's Avatar
    Join Date
    May 2001
    Location
    g0t r00t?
    Posts
    461
    find stack location find the next availble page that isnt commited downwards, alllocate some below that... or make your own stack.
    I know a lot oF Vb, expert in C++, and i think in assembly.
    MSVC++6.NET
    vb6
    masm
    Windowz Xp
    I find my self using this a lot in C++

    __asm {
    }

  6. #6
    Guru Yonatan's Avatar
    Join Date
    Apr 1999
    Location
    Israel
    Posts
    892
    For one, you could surely avoid the 2 gotos in your code by changing them to a set of whiles, ifs and breaks, possibly adding one or two boolean variables... (Change the goto to { x=true; break; } or similar)

  7. #7
    transcendental analytic kedaman's Avatar
    Join Date
    Mar 2000
    Location
    0x002F2EA8
    Posts
    7,221
    I don't think recursion would be critical, the depth of subdirectories can't go past 256 or something like that. Reading the harddrives is a slow process enough to make the recursion overhead negligible.
    If you have any local variables you don't need to include in the stack each time, make them static.
    Use
    writing software in C++ is like driving rivets into steel beam with a toothpick.
    writing haskell makes your life easier:
    reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
    To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

  8. #8

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594
    So basically, given the rather low recursion depth of a directory search, I can use recursion?

    Ok, thanks.

    Yonatan: I know, but as I said I don't like such flags. Even less than gotos.
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  9. #9
    Guru Yonatan's Avatar
    Join Date
    Apr 1999
    Location
    Israel
    Posts
    892
    Originally posted by kedaman
    the depth of subdirectories can't go past 256 or something like that.
    That depends on the file system.
    Reading the harddrives is a slow process enough to make the recursion overhead negligible.
    What about RAM drives?

  10. #10
    Frenzied Member
    Join Date
    Jul 2002
    Posts
    1,370
    FWIW -

    In VMS's lib$findfile - which NT's FindFirstFile is based on - there is a context pointer. Win 9X FindFirstFile has one as well.

    If you maintain your own context pointer - a pointer to a doubly linked list - the list tells you where you are and where you have come from, so you avoid recursion, you simply iterate, and maintain the linked list to tell you where you are, where you need to go in either direction (backwards or forwards).

    FindClose cleans up the memory associated with FindFirstFile's context heap.

    There is a little bit of discusion about this on the NT Native API page here:

    http://www.sysinternals.com/ntw2k/info/ntdll.shtml

  11. #11

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594
    I'm trying to stay compatible with both the NT and 9x strain. And I try to get along without accessing their inner workings.

    If the app I'm writing wasn't designed to be redistibutable without any runtimes (I'm going to statically link against MFC) then I'd use the SearchTreeForFile function from DbgHelp.dll.
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  12. #12
    transcendental analytic kedaman's Avatar
    Join Date
    Mar 2000
    Location
    0x002F2EA8
    Posts
    7,221

    Re: Avoiding recursion at all costs?

    Quote Originally Posted by jim mcnamara
    FWIW -

    In VMS's lib$findfile - which NT's FindFirstFile is based on - there is a context pointer. Win 9X FindFirstFile has one as well.

    If you maintain your own context pointer - a pointer to a doubly linked list - the list tells you where you are and where you have come from, so you avoid recursion, you simply iterate, and maintain the linked list to tell you where you are, where you need to go in either direction (backwards or forwards).

    FindClose cleans up the memory associated with FindFirstFile's context heap.

    There is a little bit of discusion about this on the NT Native API page here:

    http://www.sysinternals.com/ntw2k/info/ntdll.shtml
    Hi jim,

    using these context pointers (i am pushing them on a stack), can you retrieve their filedata, as to findfirstfile the subfolder? I could of course use the previous pointer and then use findnextfile but that doesn't work out with the first one..
    Use
    writing software in C++ is like driving rivets into steel beam with a toothpick.
    writing haskell makes your life easier:
    reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
    To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

  13. #13

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Re: Avoiding recursion at all costs?

    Nothing for an April Fool's joke like waking a two-year-old thread
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  14. #14
    transcendental analytic kedaman's Avatar
    Join Date
    Mar 2000
    Location
    0x002F2EA8
    Posts
    7,221

    Re: Avoiding recursion at all costs?

    I just happened to find this searching for findfirstfile
    Use
    writing software in C++ is like driving rivets into steel beam with a toothpick.
    writing haskell makes your life easier:
    reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
    To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

  15. #15

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Re: Avoiding recursion at all costs?

    Of course, these last two years I have learned that avoiding recursion at all cost, as I'm doing above, is a BAD thing. Tree iteration is inherently recursive.
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  16. #16
    transcendental analytic kedaman's Avatar
    Join Date
    Mar 2000
    Location
    0x002F2EA8
    Posts
    7,221

    Re: Avoiding recursion at all costs?

    not so sure about that.. doing recursion will always add some performance overhead. In a way all iteration is recursive, but that is in the abstract sense, not in the sense of recursive function calls. Tree iteration is the same, the stack however can be implemented without using function calls. In the abstract sense both do the same thing, but performance wise it should be better with your own stack.
    Use
    writing software in C++ is like driving rivets into steel beam with a toothpick.
    writing haskell makes your life easier:
    reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
    To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

  17. #17

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Re: Avoiding recursion at all costs?

    There is a point where managing your own stack takes more time than the CPU managing the system stack. You still require branches, you still require memory. Only, with your own stack it's quite likely that the memory will be complicated heap memory and not the already available system stack, and the branches might be harder for the CPU to predict. The fact that it's a recursive call ensures locality of reference, while the stack handling code just might make the function too big for the cache.

    And of course, not managing your own stack makes the code a lot more understandable.
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  18. #18
    transcendental analytic kedaman's Avatar
    Join Date
    Mar 2000
    Location
    0x002F2EA8
    Posts
    7,221

    Re: Avoiding recursion at all costs?

    hmm there is something in what you are saying, the stack i'm using is using heap memory, but how does the system stack avoid being blown then? It wouldn't be such a big deal to make a stack that doesn't use the heap, if only I could avoid the risk to have it blown. Another thing with recursion is that variables that don't change need not be on the stack, and taking them out makes your code less readable.
    Use
    writing software in C++ is like driving rivets into steel beam with a toothpick.
    writing haskell makes your life easier:
    reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
    To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width