Useful Recursion Example - Getting Directory Size

What is Recursion?

If you've been programming for a long time already but still haven't tapped into recursion, no one can blame you. Not many programmers use or know about recursion because of several reasons. First, often times you won't find it in crash course books or online tutorials for newbies. So programmers who jump started their careers using these crash courses wouldn't find out about it until they learn further advanced methods. Or maybe like me, you already know about it but couldn't find a use for it. Many recursive statement implementations can be done using loops. While loop implementations can be a few lines more than recursive statements, loops are often more efficient and the whole process is easier to digest.

Basically, when you create a recursive function, you define a function that calls itself within the definition. Below, you will see a function definition that calls itself. The sample codes I will use in this article will all be PHP (but recursion is applicable in almost all programming languages). I made this example as simple as I can so it's easy to understand for the newbies out there.

PLAIN TEXT
PHP:
  1. // Define the recursive funciton
  2. function count_up($val) {
  3.     if ($val<10) {
  4.         echo $val;
  5.         $val++;
  6.         // Calling the function within
  7.         // the definition
  8.         count_up($val);
  9.     }
  10. }
  11. // Let's put it to test
  12. count_up(1);

Focus on the function definition. You'll notice it does 4 things:

  • It checks whether the given parameter is less than ten (10). If it is less than 10, it proceeds with the other three steps. If not (the parameter is greater than 10) it does nothing.
  • It prints out the given parameter on the screen.
  • It then adds 1 to the value of the given parameter.
  • And finally, it calls itself.

When called and given the parameter one (1), the function will simply display the numbers one (1) to nine (9) in the screen. So here you'll notice it's just like a loop. Like I said earlier, many recursion implementations can be done using loops. And just like loops, if you are not careful with your coding, you can end up making the dreaded logic error - the infinite loop. When done using loop, the example above will look like this:

PLAIN TEXT
PHP:
  1. // Define the NON-recursive function
  2. function count_up($val) {
  3.     for ($i=$val; $i<10; $i++) {
  4.         echo $i;
  5.     }
  6. }
  7. // Let's put it to test
  8. count_up(1);

Here, the loop example (using for) has a fewer lines than the recursive one. But in some cases, recursion statements will be much shorter code than loop implementations.

Recursion Example - Getting Directory Size

If the reason you ended up in this post is because you're looking for tutorials on recursion, most likely, you already came across tutorials where the example is about factorials and the Fibonacci sequence or the Pascal's triangle. Almost every time you go to a lesson where the topic is recursion, the examples are the ones that I mention. So let's do something different, a bit more exciting, and you will find useful - getting a directory's total file size. The code of this can be found below. I've placed lots of comments along the way but you'll still find some explanation after the sample code.

PLAIN TEXT
PHP:
  1. function getdirsize($dir) {
  2.     // Initialize the size value
  3.     $size = 0;
  4.     // Get the files and directories
  5.     // inside the given directory
  6.     $files = scandir($dir);
  7.     // Loop through the files
  8.     foreach ($files as $file) {
  9.         // Filter-out .. and .
  10.         if (strlen(str_replace('.', '', $file))>0) {
  11.             if (is_dir($dir.'/'.$file)) {
  12.                 // If the item is a directory
  13.                 // run this function again and
  14.                 // get the size of the files inside
  15.                 $size += getdirsize($dir.'/'.$file);
  16.             } else {
  17.                 // If it's a file, calculate the size
  18.                 // and add it to the size variable
  19.                 $size += filesize($dir.'/'.$file);
  20.             }
  21.         }
  22.     }
  23.     // Finally, return the calculated size
  24.     return $size;
  25. }

Basically, what this function does is it goes inside the given directory and looks at all the items inside it. If the item is a file, it simply gets the file size using the PHP function, "filesize", and adds it to the main variable. If it's a directory, it runs itself to get the size of all the items inside. Imagining it, you'll realize it acts like web crawler following every links in the page and reading the pages. But this one crawls inside all the directories and gets the file sizes of the files.

Can you imagine writing this function using all loops without recursion?

Tags: , ,

Posted on: June 4, 2008     Filed under: PHP

Comments

No Comments

Leave a reply

Name *

Mail *

Website