Recursive Procedures that return values

1. The recursive procedures in the previous lab used recursion to traverse a file system and print information about the system.

   Recursive procedures can also return information to be used by the calling procedure.

   The classic example of a recursive procedure is calculating the factorial of a number.

   The factorial is used in statistics & probability for calculating the number of combinations in a set of data.

   It's created by calculating the product of all the integers between the given number and 1:

   For example, the factorial of 3 is 6:

   
   3 * 2 * 1
   

   And the factorial of 4 is 24:

   
   1 * 2 * 3 * 4
   

   This procedure will calculate a factorial:

   
   ################################################################
   # proc factorial {num}--   
   #    Return the factorial of a number
   # Arguments
   #   num   Value to calculate the factorial of
   #
   # Results
   #   No side effects
   #
   proc factorial {num} {
     if {$num == 1} {return 1}
     return [expr $num * [factorial [expr {$num-1}]]]
   }
   

   The double-factorial is created by calculating the product of all the odd or even numbers between 1 (or 2) and the given value:

   The double factorial of 5 is 15:

   
   5 * 3 * 1
   

   The double factorial of 4 is 8:

   
   4 * 2 * 1
   

   Modify the factorial procedure to return a double-factorial.

   solution

2. In order to test a file system traverser, we need a controlled file system to browse.

   Modify the solution to exercise 1 in the previous lab to create different files:

   Create 3 files in each folder -

   	File Name	Contents
   fileA.dat	12345
   fileB.txt	1234567
   fileC.txt	$folderName

   solution

3. This procedure (from the lecture) returns the total number of bytes used by files with names that match a pattern.

   
   ################################################################
   # proc findSpaceUsed {path pattern}--
   #    Returns the total number of bytes used by files that match
   #  a pattern
   # Arguments
   #   path        The file path to check
   #   pattern     A pattern to use to identify files
   # 
   # Results
   #   No side effects.  Process is recursive.
   #
   proc findSpaceUsed {path pattern} {
     set total 0
     foreach item [glob -nocomplain $path/*] {
       if {[file type $item] eq "directory"} {
         set total [expr {$total + [findSpaceUsed $item $pattern]}]
       } else {
         if {[lsearch [file tail $item] $pattern] == 0} {
         set total [expr {$total + [file size $item ]}]
         }
       }
     }
     return $total
   }
   

   This procedure tells you how many bytes the files are using, but does not tell you how much of the disk is being consumed.

   Disk drives allocate space in chunks - usually a multiple of 2 bytes. Common block sizes are 512 bytes (for older or small devices) or 4096 bytes (for newer and larger devices).

   So, 3 files with one character in each file looks like 3 bytes of file space, but is actually 3 blocks (perhaps 12288 bytes) of disk space.

   Modify the findSpaceUsed procedure to take another argument, the number of bytes in a block, and return the number of blocks used by the files.

   solution

4. A recursive procedure can return a list as well as a single value.

   It's sometimes useful to characterise a file system for how many files, how many subdirectories, how many links, etc exist.

   Starting with the file traversing procedure in the previous example write a program that will report the total number of files, subdirectories and links in the file system that starts at a given point (ie - the tmp folder created in the first exercise.)

   When it examines this tmp folder, the procedure should return this list:

   {3 12 0}

   which represents 3 subdirectories (tmp1, tmp2 and tmp3) and 12 files (fileA.dat, fileB.txt and fileC.txt in each tmp and each subfolder.

   You can postprocess that list with a foreach loop to generate output like this. Use two variables and two lists in the foreach loop.

   
   Subdirs : 3
   Files : 12
   Links : 0
   

   The trivial solution to the problem has a bunch of repeated code. (The 2 lines that are commented out in the file branch of the solution) Notice how the code becomes easier to read when the repeated lines are removed and the functionality is put into a procedure.

   solution

5. The previous exercise returns the total number of folders. It would be useful to know the greatest depth as well.

   This is a little trickier, but you can modify the previous solution to also return the maximum depth. You'll need to add a new field to the list (for max depth) and a bit more logic to track it.