2,443
个编辑
更改
跳到导航
跳到搜索
第1,053行：
第1,053行： − Multiply recursive problems are inherently recursive, because of prior state they need to track. One example is [[tree traversal]] as in [[depth-first search]]; though both recursive and iterative methods are used,<ref>{{cite web| title=Depth First Search (DFS): Iterative and Recursive Implementation| publisher=Techie Delight| date=2018| url=http://www.techiedelight.com/depth-first-search/}}</ref> they contrast with list traversal and linear search in a list, which is a singly recursive and thus naturally iterative method. Other examples include [[divide-and-conquer algorithm]]s such as [[Quicksort]], and functions such as the [[Ackermann function]]. All of these algorithms can be implemented iteratively with the help of an explicit [[stack (data structure)|stack]], but the programmer effort involved in managing the stack, and the complexity of the resulting program, arguably outweigh any advantages of the iterative solution. −
→多重递归问题
===多重递归问题===
===多重递归问题===
多重递归问题本质上是递归的，因为它们需要跟踪之前的状态。一个例子是深度优先搜索中的树遍历。虽然可以同时使用了递归和迭代方法<ref>{{cite web| title=Depth First Search (DFS): Iterative and Recursive Implementation| publisher=Techie Delight| date=2018| url=http://www.techiedelight.com/depth-first-search/}}</ref>，但它们与单重递归的列表遍历和列表中的线性搜索相比，后者是一种自然的迭代方法。其他例子包括分治算法(如快速排序)和函数(如Ackermann函数)。所有这些算法都可以在显式栈的帮助下迭代地实现，但是程序员在管理栈方面所付出的努力，以及结果程序的复杂性，无疑超过了迭代解决方案的任何优势。
多重递归问题本质上是递归的，因为它们需要跟踪之前的状态。一个例子是深度优先搜索中的树遍历。虽然可以同时使用了递归和迭代方法<ref>{{cite web| title=Depth First Search (DFS): Iterative and Recursive Implementation| publisher=Techie Delight| date=2018| url=http://www.techiedelight.com/depth-first-search/}}</ref>，但它们与单重递归的列表遍历和列表中的线性搜索相比，后者是一种自然的迭代方法。其他例子包括分治算法(如快速排序)和函数(如Ackermann函数)。所有这些算法都可以在显式栈的帮助下迭代地实现，但是程序员在管理栈方面所付出的努力，以及结果程序的复杂性，无疑超过了迭代解决方案的任何优势。
===重构递归===
===重构递归===