作者：wangey

The tree-traversal algorithms that we considered in Recursion and Trees～ Mathematical Properties of Trees and Tree Traversal exemplify the basic fact that we are led to consider recursive algorithms for binary trees, because of these trees’ very nature as recursive structures. Many tasks admit direct recursive divide-and-conquer algorithms, which essentially generalize the traversal algorithms. We process a tree by processing the root node and (recursively) its subtrees; we can do computation before, between, or after the recursive calls (or possibly all three). 继续阅读“Recursion and Trees～ Recursive Binary-Tree Algorithms”

Before beginning to consider tree-processing algorithms, we continue in a mathematical vein by considering a number of basic properties of trees. We focus on binary trees, because we use them frequently throughout this series.  继续阅读“Recursion and Trees～ Mathematical Properties of Trees and Tree Traversal”

Trees are a mathematical abstraction that play a central role in the design and analysis of algorithms because

• We use trees to describe dynamic properties of algorithms.
• We build and use explicit data structures that are concrete realizations of trees.

We have already seen examples of both of these uses. We designed algorithms for the connectivity problem that are based on tree structure in 算法：C语言实现～连通性问题, and we described that call structure of recursive algorithms with tree structures in Recursion and Trees～ Divide and Conquer and Recursion and Trees～ Dynamic Programming. 继续阅读“Recursion and Trees～ Trees”

An essential characteristic of the divide-and-conquer algorithms that we considered in Recursion and Trees～ Divide and Conquer is that they partition the problem into independent subproblems. When the subproblems are not independent, the situation is more complicated, primarily because direct recursive implementation of even the simplest algorithms of this type can require unthinkable amounts of time. In this article, we consider a systematic technique for avoiding this pitfall for an important class of problems. 继续阅读“Recursion and Trees～ Dynamic Programming”

In Recursion and Trees～ Recursive Algorithms we have discussed the relationship between mathematical recurrences and simple recursive programs, and we consider a number of examples of practical recursive programs. In this article we examine the fundamental recursive scheme known as divide and conquer, which we use to solve fundamental problems in several later sections. 继续阅读“Recursion and Trees～ Divide and Conquer”

The concept of recursion is fundamental in mathematics and computer science. The simple definition is that a recursive program in a programming language is one that calls itself (just as a recursive function in mathematics is one that is defined in terms of itself). A recursive program cannot call itself always, or it would never stop (just as a recursive function cannot be defined in terms of itself always, or the definition would be circular); so a second essential ingredient is that there must be a termination condition when the program can cease to call itself (and when the mathematical function is not defined in terms of itself). All practical computations can be couched in a recursive framework. The study of recursion is intertwined with the study of recursively defined structures known as trees. We use trees both to help us understand and analyze recursive programs and as explicit data structures. 继续阅读“Recursion and Trees～ Recursive Algorithms”