官术网_书友最值得收藏!

Recursive structures

The find command on Linux (and the dir /s command on Windows) recursively descends into a directory; if there are a few subdirectories within command, then it descends into each subdirectory, one by one. If the subdirectories, in turn, have subdirectories, command goes into each one and repeats the process all over again till all the directories are traversed. Let's have a look at the following directory:

Figure 3.1: A directory tree is a recursive structure

Given this directory, try the following command:

 % find ./tmp -type f -exec wc -c {} \;

The find command starts at the tmp directory and applies the wc command to each regular file (so for this example, skip directories).

The command enters in tmp and finds a and c. As these are directories, the flow enters a first, and finds b and one.txt. As directory b is empty, it looks at one.txt for which the predicate type f is true. So, the characters are counted for one.txt, and then the flow comes back to a and recurs into c. The process continues till every node in the directory tree is visited; also, every node is visited once and only once. Now, if you look carefully, when we come to node a, we have the same problem to solve as when we started with tmp. This problem is inherently recursive. This is the essence of recursion—we keep reducing the problem by dividing the dataset into smaller and smaller pieces. At some point though, we need to look at solving the problem (counting characters in regular files in our case). In our case, when we don't have any more directories to recur into, forms a base case with following cases:

  • A subdirectory is empty—the flow just returns in this case.
  • The note is not a directory at all but a regular file (one.txt). We perform the operation (count characters) and return.

The sub-problems that are solved directly without dividing it any further. Such base cases allow the algorithm to terminate eventually.

In the previous chapter, we looked at the binary tree traversal method. When the traversal flow hits the Null object, it terminates the traversal. This is a base case. Similarly, when the insertion flow hits the Null object, it adds the new node, forming another base case. When the traversal hits an intermediate node, we have a recursive case.

主站蜘蛛池模板: 伊春市| 渭南市| 社会| 交城县| 元江| 垫江县| 虹口区| 托里县| 兴国县| 尉犁县| 十堰市| 乌海市| 安阳市| 嘉峪关市| 乡城县| 元朗区| 泰兴市| 静宁县| 卓资县| 兴山县| 天津市| 富阳市| 南陵县| 晋江市| 五指山市| 靖安县| 德安县| 黄石市| 伊春市| 竹北市| 和田市| 嫩江县| 托克逊县| 潞西市| 饶平县| 四川省| 句容市| 曲松县| 巨野县| 临海市| 巴里|