We can make a function and we can call a function. We can have code inside one function that calls a different function. So, we can have function A call function B. We can have function B call function C, function C call functions D, E, F, G and so on.
Fig 5.4.1: Functions calling other functions
But we can also have a function that calls itself. That might not seem to make sense. It might even seem like a recipe for an infinite loop, but it's not that. What functions allow us to do is a very powerful programming technique called recursion. It’s not something you need all the time, but there are certain problems in programming where recursion is the best and the easiest way to get your result. Let's go through an example.
I'm going to do this, all in pseudocode. We're focusing here on the idea, we do not need specific syntax. This can be done in any language. We'll begin without recursion. Imagine I've been asked to write a function that takes one parameter, the name of a folder or directory on a hard drive. I need to look inside that folder and go through all the items one by one and write out the names of any MP3 files. Fig 5.4.2.
Fig 5.4.2: A “for each” loop placed inside the pseudocode to iterate around all files and detect mp3 files
So even in this pseudocode, I'm using a for each loop found in most languages. This is a loop that will iterate around however many items are in the folder. For each item I then ask is it an MP3? If it is, we print out the name of that item. That's it. This is absolutely fine. If we call this function, passing in the name of a folder (see Fig 5.4.3),
Fig 5.4.3: Calling the function and passing in the name of the folder
it'll take that parameter and then start to go through every item in that folder, whether that's 50 items, 5,000 items or more, and write out the name of each MP3. But there's a problem.
This folder might have a sub-folder. It might or might not. But if it does, we want to go inside that sub-folder too and list all the MP3s inside it. Okay. I think that doesn't sound too bad. Here's one way I might be tempted to deal with this.
We're already iterating around every item in the folder, and a sub-folder is a kind of item. So, instead of just asking if every item is an MP3, I'll add code to ask if every item is a folder. See Fig 5.4.4.
Fig 5.4.4: A code is added to ask if every item is a folder
If it is, I'm going to repeat the code I'm already using that will iterate around inside that sub-folder. So, what we're doing is taking the code that already worked and nesting it down inside another level, See Fig 5.4.5.
Fig 5.4.5: Nesting a working code down inside another level
This would actually work. It works as long as there's only two possible levels in the folder. But there's a problem with folders on a hard drive which is completely unpredictable. Reality gets in the way. We don't know how far the nesting goes. Maybe it's two levels deep, maybe it's 10 or 20 levels deep. I would have to write 20 levels of nested code, one inside the other, hoping that I've added enough to deal with all the possible options. That doesn't work for me!
Now let’s go back to the version that works on one level (Fig 5.4.2). Here's how I changed it to use recursion. When we go through each item in the folder, I'll add code to check if any item is itself another folder. See Fig 5.4.6.
Fig 5.4.6: More code is added to ask if an item itself is another folder
If it is, this function will call itself. See the last two lines of code in Fig 5.4.7.
Fig 5.4.7: In the last line of this code, the function “listMP3files” calls itself
So, we'd begin with a call to that normal top-level folder. We'd go into that folder and if we had a more complex set up, a more complex bunch of directories, we'll hit the for each loop. We'll go through each item and whenever we find a sub-folder we'll make that recursive function call.
Fig 5.4.8: Complete code where recursion is used to list all MP3 files in any level of folder structure.
We will call ourselves, but this time passing in the name of the sub-folder, so this function just begins again working its way through that sub-folder. This is recursion!
Now this code will work with one level. It'll work with two levels. It will work with 50 levels of incredibly convoluted folder structure. It will just work. It'll find every MP3 in every possible combination. A folder structure is a classic example of where recursion is useful.
It's useful for anything where you have unpredictable amounts of items and unpredictable depth, such as navigating a company organization chart, exploring the tags in a webpage, or finding all the moves for a chess piece on a chess board. There are so many problems where recursion is useful as much as anything.
I want to cover it here to expose you to this idea that in programming you will find these techniques that might sound intimidating, that take a few minutes to wrap your head around, but they lead to a solution that's easier to write and requires much less code than any of the alternative ways of fixing this problem.