370
个编辑
更改
跳到导航
跳到搜索
第459行：
第459行： + + + + + + − + 第484行：
第490行： − + − 第528行：
第533行： + + + + + + 第543行：
第554行： + 第597行：
第609行： + + + + + + 第604行：
第622行： + − 最大公约数的递归关系，其中<math>x \% y</math>表示余下的 <math>x / y</math>：+ + + 第612行：
第633行： − ! Computing the recurrence relation for x = 27 and y = 9: − + 第622行：
第642行： − ! Computing the recurrence relation for x = 111 and y = 259: − + 第663行：
第682行： + + + + + 第678行：
第702行： + − 迭代算法需要一个临时变量，即使给定了欧几里得算法的知识，虽然两种算法的步骤非常相似，但要通过简单的检查来理解其过程是比较困难的。+ + + + + − ====Towers of Hanoi==== − 河内塔 − [[File:Tower of Hanoi.jpeg|thumb|Towers of Hanoi]] − 河内塔 第693行：
第718行： − + + − ''Function definition'': 第704行：
第729行： − ''Recurrence relation for hanoi'':+ − 河内的递归关系：+ + − + − − 第728行：
第752行： + 第745行：
第770行： + + + + + + 第753行：
第784行： + − 虽然不是所有的递归函数都有明确的解，但河内塔序列可以简化为一个明确的公式。+ − ! An explicit formula for Towers of Hanoi: − 河内塔楼的明确公式：+ 第775行：
第806行： − In general: + − 通常: − h<sub>n</sub> = 2<sup>n</sup> - 1, 所有n >= 1 − ====Binary search==== − + − + − 在这个算法中使用了递归，因为每通过一次，就会把旧的数组切成两半，创建一个新的数组。然后递归地调用二进制搜索过程，这次是在新的（更小的）数组上。通常情况下，数组的大小是通过操作开始和结束索引来调整的。该算法表现出对数的增长顺序，因为它基本上是将问题域一分为二。+ 第801行：
第829行： − 以适当的初始条件调用二分搜索 − 输入 − data是按升序排列的整数数组， − toFind是要搜索的整数 − count是数组中元素的总数 − 输出 − 二分搜索的结果 + + + + + + + + + + + 第826行：
第858行： − 二分搜索算法 − − 输入： + + + + + + + + + − toFind is the integer to search for, − start is the minimum array index, − end is the maximum array index − OUTPUT: − position of the integer toFind within array data, − -1 if not found + − 如果未找到则为-1 第862行：
第894行： − + − 递归数据结构（结构递归）+ − 递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以根据运行时的要求动态地增长到理论上的无限大小；相反，静态数组的大小必须在编译时设定。+ + − + + − + + − 只要程序员从数据定义中导出模板，函数就会采用结构递归。也就是说，函数主体中的递归会消耗某个给定复值的直接部分。+ − + − 链表+ − 下面是一个链接列表节点结构的C语言定义。特别注意节点是如何从自身出发来定义的。结构节点的 "下一个 "元素是指向另一个结构节点的指针，实际上是创建了一个列表类型。+ − + − + − <syntaxhighlight lang="C"> − 结构 节点 − { − int 数据; // 一些整数数据 − 结构 节点 *next; // 指向另一个结构节点的指针 − }; − </syntaxhighlight> − 由于结构节点数据结构是递归定义的，因此对其进行操作的过程可以自然地作为递归过程实现。下面定义的list_print过程沿着列表进行遍历，直到列表为空(即，列表指针的值为NULL)。对于每个节点，它打印数据元素(一个整数)。在C语言的实现中，列表在list_print过程中保持不变。+ − + − + − + − <syntaxhighlight lang="C"> − void list_print(struct node *list) − { − if (list != NULL) // base case − { − printf ("%d ", list->data); // print integer data followed by a space − list_print (list->next); // recursive call on the next node − } − } − </syntaxhighlight> − + − 二叉树+ 第948行：
第966行： − + − + − + 第957行：
第975行： + 第970行：
第989行： − + 第985行：
第1,004行： − 上面的例子说明了二叉树的按顺序遍历。二分搜索树是二叉树的一种特殊情况，其中每个节点的数据元素是按顺序排列的。+ + + + − ====Filesystem traversal==== − 文件系统遍历 − 由于文件系统中的文件数量可能会发生变化，所以递归是遍历并枚举其内容的唯一实用方法。遍历文件系统与树形遍历非常相似，因此树形遍历背后的概念也适用于遍历文件系统。更具体地说，下面的代码将是一个文件系统的预排序遍历的示例。+ 第1,036行：
第1,056行： − 这段代码至少在某种程度上融合了递归和迭代之间的界限。本质上，它是一个递归的实现，这是遍历文件系统的最佳方式。它也是直接递归和间接递归的一个例子。'''<font color=''32CD32''>方法 "rtraverse "是纯粹的直接例子，方法 "traverse "是间接的，它调用 "rtraverse"。</font>'''这个例子不需要 "基本情况"，因为在给定的文件系统中总会有一些固定数量的文件或目录。+
→递归程序
|}
|}
{| class="wikitable"
|-
! [[伪代码]] (递归):
|-
|
'''函数''' 阶乘是:<br />
'''函数''' 阶乘是:<br />
'''输入''': 整数 ''n'' 即 ''n'' >= 0<br />
'''输入''': 整数 ''n'' 且 ''n'' >= 0<br />
'''输出''': [''n'' × (''n''-1) × (''n''-2) × … × 1]
'''输出''': [''n'' × (''n''-1) × (''n''-2) × … × 1]
<br />
<br />
{| class="wikitable"
{| class="wikitable"
|-
|-
! Computing the recurrence relation for n = 4:
!计算n = 4的递归关系：
计算n = 4的递归关系：
|-
|-
|}
|}
{| class="wikitable"
|-
! 伪代码(递归):
|-
|
'''函数''' 阶乘是:<br />
'''函数''' 阶乘是:<br />
'''输入''': 整数 ''n'' ，使得 ''n'' >= 0<br />
'''输入''': 整数 ''n'' ，使得 ''n'' >= 0<br />
<br />
<br />
'''结束''' 阶乘
'''结束''' 阶乘
|}
The imperative code above is equivalent to this mathematical definition using an accumulator variable {{math|<var>t</var>}}'':
The imperative code above is equivalent to this mathematical definition using an accumulator variable {{math|<var>t</var>}}'':
|}
|}
{| class="wikitable"
|-
! [[伪代码]] (递归):
|-
|
'''函数''' gcd 是:
'''函数''' gcd 是:
'''输入''': 整数 ''x'', 整数 ''y'' 使得 ''x'' > 0 且 ''y'' >= 0
'''输入''': 整数 ''x'', 整数 ''y'' 使得 ''x'' > 0 且 ''y'' >= 0
<br />
<br />
'''结束''' gcd
'''结束''' gcd
|}
[[Recurrence relation]] for greatest common divisor, where <math>x \% y</math> expresses the [[remainder]] of <math>x / y</math>:
[[Recurrence relation]] for greatest common divisor, where <math>x \% y</math> expresses the [[remainder]] of <math>x / y</math>:
下面式最大公约数的递归关系，其中<math>x \% y</math>表示余下的 <math>x / y</math>：
:<math>\gcd(x,y) = \gcd(y, x \% y)</math> if <math>y \neq 0</math>
:<math>\gcd(x,y) = \gcd(y, x \% y)</math> if <math>y \neq 0</math>
:<math>\gcd(x,0) = x</math>
:<math>\gcd(x,0) = x</math>
{| class="wikitable"
{| class="wikitable"
|-
|-
计算x = 27和y = 9的递归关系：
!计算x = 27和y = 9的递归关系：
|-
|-
= 9
= 9
|-
|-
计算x = 111和y = 259的递归关系：
!计算x = 111和y = 259的递归关系：
|-
|-
|}
|}
{| class="wikitable"
|-
! 伪代码(循环):
|-
|
'''函数''' gcd 是:<br />
'''函数''' gcd 是:<br />
'''输入''': 整数 ''x'', 整数 ''y'' 使得 ''x'' >= ''y'' 且 ''y'' >= 0
'''输入''': 整数 ''x'', 整数 ''y'' 使得 ''x'' >= ''y'' 且 ''y'' >= 0
<br />
<br />
'''结束''' gcd
'''结束''' gcd
|}
The iterative algorithm requires a temporary variable, and even given knowledge of the Euclidean algorithm it is more difficult to understand the process by simple inspection, although the two algorithms are very similar in their steps.
The iterative algorithm requires a temporary variable, and even given knowledge of the Euclidean algorithm it is more difficult to understand the process by simple inspection, although the two algorithms are very similar in their steps.
迭代算法需要一个临时变量，且即使给出了欧几里得算法的知识，但要通过简单的检查来理解其过程是比较困难的，虽然两种算法的步骤非常相似。
====汉诺塔====
[[File:Tower of Hanoi.jpeg|thumb|汉诺塔]]
{{main|Towers of Hanoi}}
{{main|Towers of Hanoi}}
}}</ref> There are three pegs which can hold stacks of disks of different diameters. A larger disk may never be stacked on top of a smaller. Starting with ''n'' disks on one peg, they must be moved to another peg one at a time. What is the smallest number of steps to move the stack?
}}</ref> There are three pegs which can hold stacks of disks of different diameters. A larger disk may never be stacked on top of a smaller. Starting with ''n'' disks on one peg, they must be moved to another peg one at a time. What is the smallest number of steps to move the stack?
'''<font color="#ff8000"> 河内塔Towers of Hanoi </font>'''是一个数学难题，它的解法说明了递归的问题。有三个钉子可以固定不同直径的磁盘堆叠。一个较大的圆盘永远不能堆叠在一个较小的圆盘之上。从一个钉子上的n个磁盘开始，它们必须一次一个地移动到另一个钉子上。移动堆栈的最小步数是多少？
'''<font color="#ff8000"> 汉诺塔 Towers of Hanoi </font>'''是一个数学难题，它的解法说明了递归的思想<ref>{{harvnb|Graham|Knuth|Patashnik|1990|loc=§1.1: The Tower of Hanoi}}</ref><ref>{{harvnb|Epp|1995|pp=427–430: The Tower of Hanoi}}</ref>。有三个钉子可以固定不同直径的磁盘堆叠。一个较大的圆盘永远不能堆叠在一个较小的圆盘之上。从一个钉子上的n个磁盘开始，它们必须一次一个地移动到另一个钉子上。移动堆栈的最小步数是多少？
函数定义：
函数定义：
:<math> \operatorname{hanoi}(n) =
:<math> \operatorname{hanoi}(n) =
</math>
</math>
汉诺塔的递归关系：
:<math>h_n = 2h_{n-1}+1</math>
:<math>h_n = 2h_{n-1}+1</math>
:<math>h_1 = 1</math>
:<math>h_1 = 1</math>
{| class="wikitable"
{| class="wikitable"
|-
|-
! Computing the recurrence relation for n = 4:
!计算n = 4的递归关系：
计算n = 4的递归关系：
|-
|-
Example implementations:
Example implementations:
示例实现：
示例实现：
|}
|}
{| class="wikitable"
|-
! [[伪代码]] (递归):
|-
|
'''函数''' hanoi 是:<br />
'''函数''' hanoi 是:<br />
'''输入''': 整数 ''n'', 使得''n'' >= ''1''
'''输入''': 整数 ''n'', 使得''n'' >= ''1''
<br />
<br />
'''结束''' hanoi
'''结束''' hanoi
|}
Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula.<ref>{{harvnb|Epp|1995|pp=447–448: An Explicit Formula for the Tower of Hanoi Sequence
Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula.<ref>{{harvnb|Epp|1995|pp=447–448: An Explicit Formula for the Tower of Hanoi Sequence
}}</ref>
}}</ref>
虽然不是所有的递归函数都有明确的解，但汉诺塔序列可以简化为一个明确的公式。<ref>{{harvnb|Epp|1995|pp=447–448: An Explicit Formula for the Tower of Hanoi Sequence}}</ref>
{| class="wikitable"
{| class="wikitable"
|-
|-
!汉诺塔楼的明确公式：
|-
|-
h<sub>7</sub> = 127 = 2<sup>7</sup> - 1
h<sub>7</sub> = 127 = 2<sup>7</sup> - 1
通常:
h<sub>n</sub> = 2<sup>n</sup> - 1, for all n >= 1
h<sub>n</sub> = 2<sup>n</sup> - 1, for all n >= 1
|}
|}
二分搜索
====二分搜索====
The [[binary search]] algorithm is a method of searching a [[sorted array]] for a single element by cutting the array in half with each recursive pass. The trick is to pick a midpoint near the center of the array, compare the data at that point with the data being searched and then responding to one of three possible conditions: the data is found at the midpoint, the data at the midpoint is greater than the data being searched for, or the data at the midpoint is less than the data being searched for.
The [[binary search]] algorithm is a method of searching a [[sorted array]] for a single element by cutting the array in half with each recursive pass. The trick is to pick a midpoint near the center of the array, compare the data at that point with the data being searched and then responding to one of three possible conditions: the data is found at the midpoint, the data at the midpoint is greater than the data being searched for, or the data at the midpoint is less than the data being searched for.
'''<font color="#ff8000"> 二分搜索binary search</font>'''二分搜索算法是通过每次递归将数组切成两半来搜索排序数组中单个元素的方法。其诀窍是在数组中心附近选取一个中点，将该点的数据与被搜索的数据进行比较，然后响应三种可能的条件之一：在中点找到数据，中点的数据大于被搜索的数据，或者中点的数据小于被搜索的数据。
'''<font color="#ff8000"> 二分搜索 binary search</font>'''算法是通过每次递归将数组切成两半来搜索''有序''数组中某个元素的方法。其诀窍是在数组中心附近选取一个中点，将该点的数据与被搜索的数据进行比较，然后产生三种可能之一：在中点找到数据，中点的数据大于被搜索的数据，或者中点的数据小于被搜索的数据。
Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half. The binary search procedure is then called recursively, this time on the new (and smaller) array. Typically the array's size is adjusted by manipulating a beginning and ending index. The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass.
Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half. The binary search procedure is then called recursively, this time on the new (and smaller) array. Typically the array's size is adjusted by manipulating a beginning and ending index. The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass.
在这个算法中使用了递归，因为算法每一轮都会把旧的数组切成两半，以创建一个新的数组。然后递归地调用二分搜索过程，这次是在新的（更小的）数组上。通常情况下，数组的大小是通过操作开始和结束索引来调整的。该算法表现对数级增长复杂度，因为它基本上是将问题域对半分。
Example implementation of binary search in C:
Example implementation of binary search in C:
/*
/*
Call binary_search with proper initial conditions.
Call binary_search with proper initial conditions.
INPUT:
INPUT:
data is an array of integers SORTED in ASCENDING order,
data is an array of integers SORTED in ASCENDING order,
toFind is the integer to search for,
toFind is the integer to search for,
count is the total number of elements in the array
count is the total number of elements in the array
OUTPUT:
OUTPUT:
result of binary_search
result of binary_search
以适当的初始条件调用二分搜索
输入：
data是按升序排列的整数数组，
toFind是要搜索的整数
count是数组中元素的总数
输出：
二分搜索的结果
*/
*/
int search(int *data, int toFind, int count)
int search(int *data, int toFind, int count)
{
{
/*
/*
Binary Search Algorithm.
Binary Search Algorithm.
INPUT:
INPUT:
data is a array of integers SORTED in ASCENDING order,
data is a array of integers SORTED in ASCENDING order,
toFind is the integer to search for,
start is the minimum array index,
end is the maximum array index
OUTPUT:
position of the integer toFind within array data,
-1 if not found
二分搜索算法
输入：
data是按升序排列的整数数组，
data是按升序排列的整数数组，
toFind是要搜索的整数，
toFind是要搜索的整数，
start是最小数组索引，
start是最小数组索引，
end是最大数组索引
end是最大数组索引
输出：
输出：
整数toFind在数组数据中的位置，
整数toFind在数组数据中的位置，
如果未找到则为-1
*/
*/
int binary_search(int *data, int toFind, int start, int end)
int binary_search(int *data, int toFind, int start, int end)
</syntaxhighlight>
</syntaxhighlight>
===Recursive data structures (structural recursion)===
===递归数据结构（结构化递归）===
{{main|Recursive data type}}
{{main|Recursive data type}}
An important application of recursion in computer science is in defining dynamic data structures such as [[list (abstract data type)|lists]] and [[tree (data structure)|trees]]. Recursive data structures can dynamically grow to a theoretically infinite size in response to runtime requirements; in contrast, the size of a static array must be set at compile time.
An important application of recursion in computer science is in defining dynamic data structures such as [[list (abstract data type)|lists]] and [[tree (data structure)|trees]]. Recursive data structures can dynamically grow to a theoretically infinite size in response to runtime requirements; in contrast, the size of a static array must be set at compile time.
递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以根据运行时的要求动态地增长到理论上的无限大；相反，静态数组的大小必须在编译时设定。
<blockquote>
<blockquote>
"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms."<ref>{{harvnb|Wirth|1976|p=127}}</ref>
"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms."<ref>{{harvnb|Wirth|1976|p=127}}</ref>
"当底层问题或要处理的数据以递归方式定义时，递归算法特别合适。"
"当底层问题或要处理的数据以递归方式定义时，递归算法特别合适。"<ref>{{harvnb|Wirth|1976|p=127}}</ref>
</blockquote>
</blockquote>
The examples in this section illustrate what is known as "structural recursion". This term refers to the fact that the recursive procedures are acting on data that is defined recursively.
The examples in this section illustrate what is known as "structural recursion". This term refers to the fact that the recursive procedures are acting on data that is defined recursively.
本节的例子说明了所谓的 "结构递归"。这个术语指的是递归程序是作用于递归定义的数据。
本节的例子说明了所谓的 "结构化递归"。这个术语的意思是递''归程序作用于递归定义的数据''。
<blockquote>
<blockquote>
As long as a programmer derives the template from a data definition, functions employ structural recursion. That is, the recursions in a function's body consume some immediate piece of a given compound value.<ref name="Felleisen 2002 108"/>
As long as a programmer derives the template from a data definition, functions employ structural recursion. That is, the recursions in a function's body consume some immediate piece of a given compound value.<ref name="Felleisen 2002 108"/>
只要程序员从数据定义中导出模板，函数就会采用结构递归。也就是说，函数体中的递归会消耗给定复合值的某些部分。
</blockquote>
</blockquote>
====Linked lists====
====链表====
{{main|Linked list}}
{{main|Linked list}}
Below is a C definition of a linked list node structure. Notice especially how the node is defined in terms of itself. The "next" element of ''struct node'' is a pointer to another ''struct node'', effectively creating a list type.
Below is a C definition of a linked list node structure. Notice especially how the node is defined in terms of itself. The "next" element of ''struct node'' is a pointer to another ''struct node'', effectively creating a list type.
下面是一个链表节点结构的C语言定义。特别注意节点是如何通过自身来定义的。结构节点的 "下一个 "元素是指向另一个结构节点的指针，实际上是创建了一个列表类型。
<syntaxhighlight lang="C">
<syntaxhighlight lang="C">
struct node
struct node
{
{
int data; // some integer data
int data; // some integer data 一些整数数据
struct node *next; // pointer to another struct node
struct node *next; // pointer to another struct node 指向另一个结构节点的指针
};
};
</syntaxhighlight>
</syntaxhighlight>
Because the ''struct node'' data structure is defined recursively, procedures that operate on it can be implemented naturally as recursive procedures. The ''list_print'' procedure defined below walks down the list until the list is empty (i.e., the list pointer has a value of NULL). For each node it prints the data element (an integer). In the C implementation, the list remains unchanged by the ''list_print'' procedure.
Because the ''struct node'' data structure is defined recursively, procedures that operate on it can be implemented naturally as recursive procedures. The ''list_print'' procedure defined below walks down the list until the list is empty (i.e., the list pointer has a value of NULL). For each node it prints the data element (an integer). In the C implementation, the list remains unchanged by the ''list_print'' procedure.
由于''struct node''数据结构是递归定义的，因此对其进行操作的过程可以自然地实现为递归过程。下面定义的''list_print''过程沿着列表进行遍历，直到列表为空(即，列表指针的值为NULL)。对于每个节点，它打印数据元素(一个整数)。在C语言的实现中，列表在''list_print''过程中保持不变。
<syntaxhighlight lang="C">
<syntaxhighlight lang="C">
void list_print(struct node *list)
void list_print(struct node *list)
{
{
if (list != NULL) // base case
if (list != NULL) // base case 基本情况
{
{
printf ("%d ", list->data); // print integer data followed by a space
printf ("%d ", list->data); // print integer data followed by a space 打印数据和一个空格
list_print (list->next); // recursive call on the next node
list_print (list->next); // recursive call on the next node 递归调用下一个节点
}
}
}
}
</syntaxhighlight>
</syntaxhighlight>
====Binary trees====
====二叉树====
{{main|Binary tree}}
{{main|Binary tree}}
struct node
struct node
{
{
int data; // some integer data
int data; // some integer data 整数类型的数据
struct node *left; // pointer to the left subtree
struct node *left; // pointer to the left subtree 指向左子树的指针
struct node *right; // point to the right subtree
struct node *right; // point to the right subtree 指向右子树的指针
};
};
</syntaxhighlight>
</syntaxhighlight>
对二叉树的操作可以使用递归来实现。注意，由于有两个自引用指针（左和右），对二叉树的操作可能需要两次递归调用：
对二叉树的操作可以使用递归来实现。注意，由于有两个自引用指针（左和右），对二叉树的操作可能需要两次递归调用：
<syntaxhighlight lang="C">
<syntaxhighlight lang="C">
// Test if tree_node contains i; return 1 if so, 0 if not.
// Test if tree_node contains i; return 1 if so, 0 if not.
At most two recursive calls will be made for any given call to ''tree_contains'' as defined above.
At most two recursive calls will be made for any given call to ''tree_contains'' as defined above.
对于上面定义的''tree_contains''的任何给定调用，最多会有两次递归调用。
对于上面定义的''tree_contains''的任何给定函数调用，最多会产生两次递归调用。
<syntaxhighlight lang="C">
<syntaxhighlight lang="C">
The above example illustrates an [[Tree traversal|in-order traversal]] of the binary tree. A [[Binary search tree]] is a special case of the binary tree where the data elements of each node are in order.
The above example illustrates an [[Tree traversal|in-order traversal]] of the binary tree. A [[Binary search tree]] is a special case of the binary tree where the data elements of each node are in order.
上面的例子说明了二叉树的按顺序遍历。二分搜索树是二叉树的一种特殊情况，其中每个节点的数据元素按顺序排列。
====文件系统遍历====
Since the number of files in a [[filesystem]] may vary, [[recursion]] is the only practical way to traverse and thus enumerate its contents. Traversing a filesystem is very similar to that of [[tree traversal]], therefore the concepts behind tree traversal are applicable to traversing a filesystem. More specifically, the code below would be an example of a [[preorder traversal]] of a filesystem.
Since the number of files in a [[filesystem]] may vary, [[recursion]] is the only practical way to traverse and thus enumerate its contents. Traversing a filesystem is very similar to that of [[tree traversal]], therefore the concepts behind tree traversal are applicable to traversing a filesystem. More specifically, the code below would be an example of a [[preorder traversal]] of a filesystem.
由于文件系统中的文件数量可能会发生变化，所以递归是遍历并枚举其内容的唯一实用方法。遍历文件系统与树遍历非常相似，因此树遍历背后的概念也适用于遍历文件系统。更具体地说，下面的代码将是一个文件系统的前序遍历的示例。
<syntaxhighlight lang="Java">
<syntaxhighlight lang="Java">
This code blends the lines, at least somewhat, between recursion and [[iteration]]. It is, essentially, a recursive implementation, which is the best way to traverse a [[filesystem]]. It is also an example of direct and indirect recursion. '''<font color=''32CD32''> The method "rtraverse" is purely a direct example; the method "traverse" is the indirect, which calls "rtraverse". </font>''' This example needs no "base case" scenario due to the fact that there will always be some fixed number of files or directories in a given filesystem.
This code blends the lines, at least somewhat, between recursion and [[iteration]]. It is, essentially, a recursive implementation, which is the best way to traverse a [[filesystem]]. It is also an example of direct and indirect recursion. '''<font color=''32CD32''> The method "rtraverse" is purely a direct example; the method "traverse" is the indirect, which calls "rtraverse". </font>''' This example needs no "base case" scenario due to the fact that there will always be some fixed number of files or directories in a given filesystem.
这段代码至少在某种程度上糅合了递归和迭代之间的界限。本质上，它是一个递归的实现，这是遍历文件系统的最佳方式。它也是直接递归和间接递归的一个例子。 '''<font color=''32CD32''> 方法 "rtraverse "是直接递归的例子，方法 "traverse "是则间接的，它调用 "rtraverse"。</font>'''这个例子不需要 "基本情况"，因为在给定的文件系统中文件和目录的数量总是有限的。
==Implementation issues==
==Implementation issues==