基于递归程序到非递归程序转换的实现

洪　莉

摘要：基于递归程序时空性能不好的缺点，提出了用非递归方法来解决递归问题的实现方法。

关键词：递归程序栈

递归技术是许多软件设计人员常用的方法，但在实际应用时，也存在一些问题，主要表现在以下两个方面：

(1)程序设计语言对递归的支持方面的限制。较典型的是FORTRAN语言，它明确规定不允许直接或间接递归。还有一些语言虽然可以使用递归，但由于没有较好的内部支持机制，因而在这方面的性能不太好，编程太麻烦，且所编程序可读性差；(2)程序运行的时间性能方面。对同一问题的求解程序，递归程序比非递归程序要花费更多的时间。

鉴于上述问题，在许多情况下，要求能写出求解问题的非递归程序。由于许多复杂问题的求解程序的递归程序比非递归程序要容易设计，因此，常常是先设计出递归程序，然后再将其转换为等价的非递归程序。转换的方法有两种。

1用循环法消除递归

循环法是利用“依赖图”进行分析和化简的。下面通过例子来说明递归程序向非递归程序的转化过程。求n!的递归程序：

借助于栈将递归程序转换为非递归程序很方便，尤其是要想将有些复杂的递归程序转换为非递归程序，如果不借助于栈，只用简单的循环方法是很难实现的。基于栈的方法，可以将任何一个递归问题对应的程序转换为一个非递归程序。

3结束语

递归程序简单、清晰、可读性好，且易于验证其正确性，但浪费空间且执行效率低，因此，有时需要把递归程序转换成非递归程序，这种转化带来的优点有，第一，有利于提高算法的时空性能：第二，有助于深刻理解递归机制，而这种理解是熟练掌握递归程序设计的必要前提。