陈韶钰 孙娟

摘要：在数据结构的教学中，我们经常用到递归，例如广义表，二叉树等，但是在课本中讲到递归算法的非递归化却寥寥数语，并且很多学生也问到这个问题。该文针对这一情况研究递归函数的非递归化。该文根据是否是尾递归进行分类，重点讲解两种不同的非递归化方法，其中一种转换成循环来实现非递归化，但是对于复杂的非尾递归则使用栈来模拟系统栈的工作方式来实现非递归化，最后给出递归和非递归化的比较，根据问题的实际情况选择是否采用递归。

关键词：递归算法;非递归化;尾递归;迭代;非尾递归;栈

中图分类号：TP3        文献标识码：A

文章编号：1009-3044（2021）13-0202-03

1 递归算法的概述

什么是递归？有这样一个非常典型的例子：从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是......递归函数就是一个直接调用自己或通过一系列的调用语句间接调用自己的函数。递归函数包含三种：第一，有很多递归定义的数学函数，例如阶乘，斐波那契数列;第二，有本身具有递归特性的数据结构，例如二叉树，广义表等;第三种有些问题递归求解比迭代求解更加简单，例如Hanoi塔问题，八皇后问题等。

此外，递归有三个要素：第一，递归边界条件：确定递归到何时终止，即递归出口;第二，递归模式：大问题如何分解为小问题的，即递归体;第三，递归的调用次数必须是有限的，每次递归调用后必须越来越接近某种限制条件。……