- 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.

- 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 - 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. - 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. - 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.

```
```