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

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

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.

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