C# Recursion With File Folder Hierarchies: Beginner's Guide

if you're someone that struggles with the concept of recursion then this video is for you hi my name is Nick centino and I'm a principal software engineering manager at Microsoft in a previous video I was showing how we could go navigate a file folder hierarchy with iteration and in this video I want to demonstrate the same idea if you want to use recursion now if you haven't seen the previous video you can go ahead and check it out up here but in this video we will focus on a recursive approach to going through the file folder hierarchy now I'm going to start off by showing you one variation of this it will still have loops inside of it but I think personally it's a little bit more easy to understand conceptually and then we're going to go ahead and remove all of the loops and see how we can make it work if that sounds interesting just a reminder to subscribe to the channel and check out that pin comment for my courses on dome train with that said let's jump over to visual studio and check out this example what we're going to be doing in this example is walking through a folder that I have on my computer that's in my Dev folder at the root of my C drive and then in a folder called choruses so that's going to be the root of what we're looking at now I have this class right here starting on line six it's going to have our recursive algorithm so if we look at the entry point to that algorithm it's just a run method it takes in a root path we're just going to do a quick check to make sure it exists but if it does we are going to start our recursive algorithm off so what we do is we pass in the root and we have a depth of zero and just to make it a little bit more obvious for this I going to put depth and actually name the argument just to help it be a little bit more straightforward here so first thing once we go into depth first recursive we have the current folder that we're dealing with and the depth that we're at I do have some console writing here so line 21 and 22 I just format some indentation and this way when we're writing out the console we can start to see the file folder hierarchy printing out as you might expect to see just so we don't have everything at the same level and it makes it even more confusing to navigate so that's all that this indentation line does here and then I just have some string formatting you'll also notice that I'm using path. getet file name on the folder itself that's just so I can get the folder portion of the path and we don't print out the whole thing just to clean it up a little bit in the output from there what I'm going to be doing is still using some amount of iteration here so you'll notice I have a for each loop we're going to ask the current folder for all of the directories and then we're going to do the recursive part which is to call the same method that we're in and if you notice the highlighting on line 26 and visual studio has also highlight the current method that we're in and it's the same method that's called on line 16 the fact that we are calling the same method that we're currently executing this is going to be the recursive part of this algorithm in this example but what you will notice is that I am increasing the depth so I'm adding one this way when we go to print indentation in the subsequent calls it will be one step further the other thing that we're doing is we're passing in the current directory from our 4 each Loop so this current directory is is not the same as the current folder that was passed in so if you think about it if I go pull up this actual uh folder that we're going to be looking at if we go into Dome train and reflection just so we have an example here if we had reflection this folder so do tr/ reflection if we were in this folder if I put it over here to make it a little bit more obvious what you'll see is that we have reflection and then code and videos as folders inside there we might be calling depth first recursive where the current folder is reflect ction but then when we're going to iterate over the directories inside of this folder the first iteration of that might have code as the first directory and then we're going to pass that into depth first recursive so then we would continue the algorithm but now we're going to be inside of this folder and you'll notice that there are a lot more folders inside of it conceptually the idea here is that we're going to keep calling this same method and keep going deeper and deeper using recursion the algorithm is going to repeat itself so I'm not going to keep explaining it until we go to debug it a little bit later but the other part to this algorithm is that we're not just dealing with the folders once we finish going deeper through all the folders once we're out of folders to iterate over this is where we're going to start printing out the files so the indentation that I'm going to use is just one deeper than the current depth of folders that way it looks like the files are nested inside the folder of course and then we write out each of those files so we're going to use another for each Loop so some more iteration we're not fully recursive yet and then we're going to print out the file name with some amount of indentation I think it'll be helpful to go ahead and run this and I'm going to show you the output in the console and then we can try explaining what's going on by seeing the console output and stepping through the file folder hierarchy in the browser this is just a brief Interruption to remind you that I do have courses available on dome train focused on C so whether you're interested in getting started in C looking for a little bit more of an intermediate course focus on object-oriented programming and some async programming or are you just looking to update your refactoring skills and see some examples that we can walk through together you can go ahead and check them out by visiting the links in the description and the comment below thanks and back to the video okay so I've gone ahead and run this and you can see that we start to have this directory structure printing out with choruses Dome train reflection and then code right so let me pull this up at the same time we're going to go up and start at the same spot so we do have inside of our courses Dome train folder right so courses then Dome train we have reflection and then code and videos you can see on the right hand side here however we notice that when we start looking at this directory structure we go from reflection to code and then we start printing out something else it's not videos right so we've gone into code however if we consider the algorithm that we have on the screen once we get into the reflection folder the first part from line 24 to line 27 is going to iterate over the folders inside of here so we will ask for code first and then we're going to call depth first or cursive again on it so that means before we touch videos at all we're going to jump into this folder and then the algorithm will repeat so it will keep repeating until we run out of folders and start doing files so now that we're in the code folder you'll notice that there's a folder right at the top here and it's dogit which means before we touch any of the other files in here or before we get to any other folders We will be starting with the first one and that just means we keep going deeper so I'm going to double click it and go in again and you'll notice same idea right so we're just going to keep repeating this algorithm so we're going to look for all the folders before we touch files and we start with the first one it's hooks so we'll go in once more and now you'll notice on my screen on the right hand side there are no more folders so if we make this a little bit more visible line 24 through line 27 once we're in the hooks folder there are no more folders so line 24 through 27 it's going to basically skip over this because there are no directories and then we're going to start printing out the files if you have a close look we'll see that apply patch message sample that's this first file here and if I scroll through the bottom on the right hand side just to prove it right there's no folders in this directory so if we scroll down a little bit lower on the left you'll notice that we get through all these files and then we go back up one level of indentation and that's the same as me jumping back out of here and then we look at the next folder and we see info and then we'll jump into that one next and there's one file so if I scroll down a little bit lower on the left you'll see we go to exclude before jumping back out now I'm not going to walk through all of the files and folders in this example because we would be here for forever but the primary idea here is that we're mixing both recursion and iteration to accomplish this example and the primary part to call out is that every time we call depth first recursive we are essentially giving another folder to go run this small algorithm over each time we go try and increase the depth and that way we can print out and have some indentation to make the formatting look a little bit easier to understand but again we're just going to repeat the same little algorithm from 19 to 34 on each folder that we come across I will make a follow-up video on this idea but generally my personal preference is that I like iterative methods over recursive methods and that's because when it comes to debug ability an overall just general understanding I'm not a huge fan of recursion it's not that I don't understand how it works I just don't enjoy it so there will be a follow-up video but what I wanted to call out is the current algorithm we have in place I'm actually content with that I actually don't mind this amount of recursion yes there are some things to consider like your call stack depth and other characteristics ICS about recursive algorithms that we could talk about but this is a healthy balance in my opinion we have some iteration that allows me to understand some more things cohesively that's just my personal opinion on it and the way we're using recursion I can easily think about this because I'm just thinking Every Time We Touch a folder in our algorithm we just want to go repeat the exact same thing so to me that makes plenty of sense so hopefully so far this example seems relatively straightforward again if you have haven't used recursion and it's a little bit confusing I do recommend you take this opportunity while the code is on the screen you can go look at how it's working you can try making your own recursive algorithm and try stepping through it what we're going to do before we look at the other variation of this is just that I'm going to go ahead and put a breakpoint in here and show you what the call stack looks like and then we're going to step out once more to explain what I mean I've added this breakpoint on line 20 and I'm going to enable it but I have a condition set on this breakpoint so what you'll notice is that I'm going to break when the depth is greater than or equal to five just so we can reach a kind of interesting point in the algorithm so I'm going to go ahead and press play and then what I'll do is look at the right hand side of my output in the bottom this this call stack and you'll see that it looks like we have a bunch of the same method calls right we see recursion depth first do depth first recursive and it's the same thing we see line 20 line 26 line 26 line 26 line 26 and line 2 6 once more right it's the same thing over and over again but if we think about it we're technically at a depth where we've gone five levels in and that means we should have six of these 1 2 3 4 5 six that's because we start at a depth of zero right so at a depth of five that's six in total if we go have a look here the current folder is going to be in this dog hooks path and that means that we've gone ahead a little bit but what I wanted to call out on my screen is like again why I don't really like recursion a lot primarily because when we're looking at what's being highlighted from Visual Studio we have the same method call a couple of times right you can see this one's highlighted this one's also highlighted right obviously we're only calling this once that's sort of the entry point to it all but when we start to look at the call stack right I get a little bit confused personally if I wanted to try debugging where an issue was I literally have to go up the call stack frames and every time I double click and go to another one you'll notice the code isn't really moving right there's no change but if we have a close look in the bottom left as I go through these so we're in choruses I'll double click this next frame we'll see Dome train and the depth goes up by one then we'll see reflection the depth goes up by one so on and so forth so if you actually like debugging this way and having a snapshot of the call stack like this awesome maybe going through recursive functions is like a great way for you to think about things personally I don't like having having them broken out like this I like having an iterative approach where I can step through things and that's just my personal preference but I wanted to show you what this looks like right so if we step through this and now we're in this current folder which is hooks if I go ask if there are any folders here there are none right so we've gone as deep as we can at this point and then we're going to go over the files and we keep stepping through blah blah blah we'll go through all the files if I do shift f11 we will step out of this I press shift f11 it might be confusing because it looks like we didn't really move but we went up one level in the call stack now when I step over this we'll see that there's another file and you can see that it was at hooks as soon as I press F10 now it's not at hooks it's at info so the info folder is a sibling to hooks they're at the same level and then we're going to go right back into it and if I press f11 to step into this we're in the same method right so it's just keeping the same context but Shifting the stack frame with the new information that we have so you might prefer this kind of approach for me it's not really my preference I just wanted to show it to you with that said we've had this algorithm in front of us that has both recursion and iteration it accomplishes navigating through the file folder hierarchy but it uses kind of both of these approaches what I'm going to do is expand this other part down below and it's the same idea but but you'll notice it's broken out slightly differently and we're going to walk through it so don't worry but the idea for this one if I can try to get as much of it on screen as I can is that in this case there are no Loops but this code is functionally equivalent so I've just called it depth first recurse of two it accomplishes the exact same thing but every time we would have had a loop what we are going to do is instead have a recursive function call and all that we're going to do if I scroll down a little bit lower you'll see that I have process files recursive and process directories recursive each one of these takes an array of files or an array of directories and an index now what that means is if we have a close look if I double click process files recursive and we see where it's highlighted if we come into process files recursive with our array of files we're going to call the same thing once again right so it's going to call itself it's going to use the same array of files but it's now indicating that we're going to be talking about the next element in the array so instead of going deeper CU that's what the first algorithm was doing right every time it would hit a folder it would go deeper in this case these are just a list of files or an array of files and we're going to be touching the siblings so we call the same method with the same collection and then we just say hey the index that we're working with it's the next one and we keep doing this but there's this check right at the top which is the base case and the base case tells us hey look if your index is essentially one more or equal to the file length so as soon as we hit that edge we're just going to stop and that means that we have some protection and we don't go out of bounds on our array so with this type of approach you do need to have a base case to terminate your recursion and the same idea is going to apply when we talk about the directories but there's a subtle difference in this case right when we Pro directories again I'm going to double click this to highlight you'll see on line 71 almost the exact same idea we're going to call itself with the collection of directories we will go over one more so we're going to go through the siblings right that we have of this directory that we're at but on line 70 so right above we're going to call the entire thing from the start so line 70 if I scroll up a little higher goes right back to the entry point of this whole recursive function and I realize this might be confusing but it's the same thing that we experienced in the first example essentially every time we get into a folder yes we have to go ask for the current folder it's subfolders and the files but Every Time We Touch a folder we have to go repeat the whole algorithm once more otherwise we would never go deeper in the first case I just wanted to show you that these two Loops so line 24 through 27 and line 30 through 33 we're basically getting rid of these two Loops essentially just by using recursive calls again so this part here that I have highlighted gets rid of the loop that looked at the files before and down here this gets rid of the loop that would have stepped over all of the folders so the fact that we call process in both cases here on 59 and 71 this is essentially acting like a loop instead of having the loop we use recursion so a little bit weird I just wanted to explain it but to prove to you that this works if I go back up to the top this is sort of our entry point to this method on this class if I put a two here instead that means that this code we don't need it anymore right because we're calling the second version of this if I go ahead and run this we should see the same type of output okay and to start things off just to prove that it's working as expected we start with ches at the Top If we think about this algorithm right the current fold that we have at the top is going to be chuses so we will go ahead and write that out rate at the top then we're going to ask for the subdirectories when we go to do that this sub directories collection is only going to have one thing in it which is Dome train now we are going to call Process directories recursive before we even ask for the files but what I wanted to call out is there aren't even files here so I'm going to fast forward a little bit through this algorithm so it gets a little bit more interesting but when we go into this folder you'll notice same thing right so every time that we go to do this when there's only one folder in here it's not super exciting but once we get into reflection okay so if we imagine that we're doing depth first recursive now the current folder is reflection on line 41 when we ask for the subdirectories of reflection we will have code and videos and you'll notice on the left within reflection we have code to start with and if we think about it if we ask for the subdirectories that means we have code in videos if I go and jump into process subdirectory so let's go ahead and look at this the first thing we're going to do is call the whole algorithm once again we're not even going to process the sibling because if you recall I mentioned that line 71 to call back into itself here this just steps through the sibling folders that we have this would be code but we're not going to go look at the next one yet we're not going to go look at videos we're actually going to go start the whole thing again so if I press F12 we're going to start the whole thing again but looking at code so let me pull this up again and this that means we're starting in here now I realize it might be a little bit confusing to follow along but if you are struggling to kind of understand how this is working I do highly recommend that you get pen and paper out and try to follow along that means you might want to rewind this video and go along with pen and paper and kind of Trace out some directory structure if you're going to go a head and write this code yourself I recommend the same thing put some break points in get some pen and paper and step through it um and you can start with a more simple directory structure as well but I do recommend pen and paper it helps tremendously if we think about this concept though every time that we have a folder inside of another folder we will keep going deeper this is what we experienced in the first version of this so that means we have a folder with subfolders it's going to result in us going deeper we have a folder with some subfolders we're going to go deeper and as I'm saying this and clicking in you'll notice that it's true on the left hand side right we had dogit which is a folder and hooks which is a folder once we get into the hooks folder there are no subfolders right so line 41 in the code for hooks when it asks for the subdirectories this will be empty that means when we go into this method this collection here will be empty if I press F12 the index is 0er to start with so is 0 greater than or equal to an empty length array this is going to be zero so yes 0 is greater than or equal to zero so we will return we stop processing any further if we didn't have this check we will basically either run into sort of infinite recursion or go outside of the bounds of an array either those things could happen depending on the order of these so you do need to have this base case let's go back up up here we know that this going to go into here and then step right back out because there are no subdirectories but when we go to ask for the files we will get an array of files back and it's going to match this collection up here okay so we're going to have all these files come back in this array and then go into process files recursive now when we go to check the index so is zero less than however many files are in that folder if I do a quick check I think it said that there are okay there's 14 files in here so is zero greater than or equal to 14 absolutely not so we will not return we're going to go print out the first one and if we check what that is apply patch message. sample it will print that and then it's going to call itself and it's going to call itself at the same depth we're not going any deeper we're still in the same folder going through each file but we're going to say the index we're looking at in this array is the next file over if I open this right we should expect to commit message. sample as the next element in the array so if we went from zero index to one index we're now at this one and that means if we call Process files recursive right it just jumps right to the same spot we're just now one over in our index so then we would check is 1 greater than or equal to 14 no so don't return let's go print out the current file and just to check what it is there we go commit m message sample so this is at the one index I'm not going to repeat this for all other 14 in here but you'll notice that if we continued it you would keep stepping through all of these until we got to the 13th index I guess technically 14 cuz we'll go one further but we check right here once we hit the 14th index we say hey look you're at the length you will be exceeding the bounds of the array if you even try so don't do it that means we terminate doing process files recursive and we start going back up personally again in my opinion I don't really like recursion because this all makes sense until I start going back up and then I go oh wait now I have to remember all the previous context it's a little bit easier with the debugger but personally this is just not how my brain likes to think through things both of these examples that we saw involve recursion it's just that in the second example that we looked at we were able to do away with the two Loops that we had right so this Loop here and this Loop here we could do away with them by just calling a method that's the same one we're in and basically giving it an updated index into the array that we're looking at hopefully this practical example made a little bit more sense than when you first got here and recursion is starting to click a little bit again don't blame yourself if it's taking a little bit more time than you're expecting to understand this it might be helpful if you go back and check that video I linked on iteration it steps through the exact same example but it uses iteration to accomplish the same type of thing now if you're interested in seeing my pros and cons sort of perspective on iteration versus recursion you can go ahead and check out this video next when it's ready thanks and I'll see you next time