370
个编辑
更改
跳到导航
跳到搜索
第633行：
第633行： − − − − 第645行：
第641行： − − 第661行：
第655行： − 第675行：
第668行： − − − 第691行：
第681行： − 第721行：
第710行： − 第767行：
第755行： − −
→递归数据结构（结构化递归）
递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以根据运行时的要求动态地增长到理论上的无限大；相反，静态数组的大小必须在编译时设定。
递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以根据运行时的要求动态地增长到理论上的无限大；相反，静态数组的大小必须在编译时设定。
<blockquote>
<blockquote>
"当底层问题或要处理的数据以递归方式定义时，递归算法特别合适。"<ref>Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 126. ISBN 978-0-13022418-7.</ref>
"当底层问题或要处理的数据以递归方式定义时，递归算法特别合适。"<ref>Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 126. ISBN 978-0-13022418-7.</ref>
</blockquote>
</blockquote>
<blockquote>
<blockquote>
只要程序员从数据定义中导出模板，函数就会采用结构递归。也就是说，函数体中的递归会消耗给定复合值的某些部分。
只要程序员从数据定义中导出模板，函数就会采用结构递归。也就是说，函数体中的递归会消耗给定复合值的某些部分。
</blockquote>
</blockquote>
};
};
</syntaxhighlight>
</syntaxhighlight>
由于''struct node''数据结构是递归定义的，因此对其进行操作的过程可以自然地实现为递归过程。下面定义的''list_print''过程沿着列表进行遍历，直到列表为空(即，列表指针的值为NULL)。对于每个节点，它打印数据元素(一个整数)。在C语言的实现中，列表在''list_print''过程中保持不变。
由于''struct node''数据结构是递归定义的，因此对其进行操作的过程可以自然地实现为递归过程。下面定义的''list_print''过程沿着列表进行遍历，直到列表为空(即，列表指针的值为NULL)。对于每个节点，它打印数据元素(一个整数)。在C语言的实现中，列表在''list_print''过程中保持不变。
}
}
</syntaxhighlight>
</syntaxhighlight>
====二叉树====
====二叉树====
下面是二叉树节点的一个简单定义。与链表的节点一样，它是按照自身递归地定义的。有两个自引用指针:left(指向左边的子树)和right(指向右边的子树)。
下面是二叉树节点的一个简单定义。与链表的节点一样，它是按照自身递归地定义的。有两个自引用指针:left(指向左边的子树)和right(指向右边的子树)。
};
};
</syntaxhighlight>
</syntaxhighlight>
对二叉树的操作可以使用递归来实现。注意，由于有两个自引用指针（左和右），对二叉树的操作可能需要两次递归调用：
对二叉树的操作可以使用递归来实现。注意，由于有两个自引用指针（左和右），对二叉树的操作可能需要两次递归调用：
上面的例子说明了二叉树的按顺序遍历。二分搜索树是二叉树的一种特殊情况，其中每个节点的数据元素按顺序排列。
上面的例子说明了二叉树的按顺序遍历。二分搜索树是二叉树的一种特殊情况，其中每个节点的数据元素按顺序排列。
====文件系统遍历====
====文件系统遍历====
}
}
</syntaxhighlight>
</syntaxhighlight>
这段代码至少在某种程度上糅合了递归和迭代之间的界限。本质上，它是一个递归的实现，这是遍历文件系统的最佳方式。它也是直接递归和间接递归的一个例子。 '''<font color=''32CD32''> 方法 "rtraverse "是直接递归的例子，方法 "traverse "是则间接的，它调用 "rtraverse"。</font>'''这个例子不需要 "基本情况"，因为在给定的文件系统中文件和目录的数量总是有限的。
这段代码至少在某种程度上糅合了递归和迭代之间的界限。本质上，它是一个递归的实现，这是遍历文件系统的最佳方式。它也是直接递归和间接递归的一个例子。 '''<font color=''32CD32''> 方法 "rtraverse "是直接递归的例子，方法 "traverse "是则间接的，它调用 "rtraverse"。</font>'''这个例子不需要 "基本情况"，因为在给定的文件系统中文件和目录的数量总是有限的。