从求解格点问题看递归算法及其与迭代循环算法的比较

递归是比迭代循环更有力的算法。一方面,每个循环算法均可找到一个等价的递归算法;另一方面,一些循环算法不能求解的问题常可用递归算法求解。格点问题便是这类问题中具有代表性的一个。 本文通过对格点问题构造有效算法来讨论:一,如何根据一个问题所固有的结构关系去选择适当的算法;二,递归算法在计算机内的实现方式及对递归程序的跟踪;三,递归算法与循环算法的比较。

RECURSIVE ALGORITHM OF LATTICE POINT PROBLEM AND COMPARISON BETWEEN IT AND ITERATON ALGORITHM

Recursion is a more powerful algorithm than iterative loop. On the one hand, for every iterative loop there is always an equivalent recursion. On the other hand, some problems, insoluble by means of iterative loop, are often solved by recursion. The Lattice Point Problem is typical one of these problems.By constructing an effective algorithm for the Lattice Point Problem, we have firstly discussed how to choose a proper algorithm depending on the inherent structural relations of a certain problem.