递归算法转换为非递归算法的技巧

文章预览

递归函数具有很好的可读性和可维护性，但是大部分情况下程序效率不如非递归函数，所以在程序设计中一般喜欢先用递归解决问题，在保证方法正确的前提下再转换为非递归函数以提高效率。 函数调用时，需要在栈中分配新的帧，将返回地址，调用参数和局部变量入栈。所以递归调用越深，占用的栈空间越多。如果层数过深，肯定会导致栈溢出，这也是消除递归的必要性之一。递归函数又可以分为尾递归和非尾递归函数，前者往往具有很好的优化效率，下面我们分别加以讨论。 尾递归函数 尾递归函数是指函数的最后一个动作是调用函数本身的递归函数，是递归的一种特殊情形。尾递归具有两个主要的特征：   1. 调用自身函数(Self-called)；   2. 计算仅占用常量 ………………………………