更改

递归算法可以用非递归的对应算法来替换<ref>{{cite web| last=Mitrovic| first=Ivan| title=Replace Recursion with Iteration| publisher=[[ThoughtWorks]]| url=https://www.refactoring.com/catalog/replaceRecursionWithIteration.html}}</ref>。替换递归算法的一种方法是用堆内存代替栈内存来模拟它们<ref>{{cite web| last=La| first=Woong Gyu| title=How to replace recursive functions using stack and while-loop to avoid the stack-overflow| publisher=CodeProject| date=2015| url=https://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and}}</ref> 。另一种方法是完全基于非递归方法来开发替换算法，这可能是一个挑战<ref>{{cite web| last=Moertel| first=Tom| title=Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick| date=2013| url=http://blog.moertel.com/posts/2013-05-14-recursive-to-iterative-2.html}}</ref> 。例如，用于通配符匹配的递归算法，如Rich Salz的wildmat算法<ref>{{cite web| last=Salz| first=Rich| title=wildmat.c| publisher=[[GitHub]]| date=1991| url=https://github.com/trevor/transmission/blob/master/libtransmission/wildmat.c}}</ref>，曾经是典型的算法。为了避免递归的缺点<ref>{{cite magazine| last=Krauss| first=Kirk J.| title=Matching Wildcards: An Algorithm| magazine=[[Dr. Dobb's Journal]]| date=2008| url=http://www.drdobbs.com/architecture-and-design/matching-wildcards-an-algorithm/210200888}}</ref>，人们开发了用于相同目的的非递归算法，如Krauss通配符匹配算法，并在收集测试和性能分析等技术的基础上逐步改进。<ref>{{cite web| last=Krauss| first=Kirk J.| title=Matching Wildcards: An Improved Algorithm for Big Data| publisher=Develop for Performance| date=2018| url=http://www.developforperformance.com/MatchingWildcards_AnImprovedAlgorithmForBigData.html}}</ref>

递归算法可以用非递归的对应算法来替换<ref>{{cite web| last=Mitrovic| first=Ivan| title=Replace Recursion with Iteration| publisher=[[ThoughtWorks]]| url=https://www.refactoring.com/catalog/replaceRecursionWithIteration.html}}</ref>。替换递归算法的一种方法是用堆内存代替栈内存来模拟它们<ref>{{cite web| last=La| first=Woong Gyu| title=How to replace recursive functions using stack and while-loop to avoid the stack-overflow| publisher=CodeProject| date=2015| url=https://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and}}</ref> 。另一种方法是完全基于非递归方法来开发替换算法，这可能是一个挑战<ref>{{cite web| last=Moertel| first=Tom| title=Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick| date=2013| url=http://blog.moertel.com/posts/2013-05-14-recursive-to-iterative-2.html}}</ref> 。例如，用于通配符匹配的递归算法，如Rich Salz的wildmat算法<ref>{{cite web| last=Salz| first=Rich| title=wildmat.c| publisher=[[GitHub]]| date=1991| url=https://github.com/trevor/transmission/blob/master/libtransmission/wildmat.c}}</ref>，曾经是典型的算法。为了避免递归的缺点<ref>{{cite magazine| last=Krauss| first=Kirk J.| title=Matching Wildcards: An Algorithm| magazine=[[Dr. Dobb's Journal]]| date=2008| url=http://www.drdobbs.com/architecture-and-design/matching-wildcards-an-algorithm/210200888}}</ref>，人们开发了用于相同目的的非递归算法，如Krauss通配符匹配算法，并在收集测试和性能分析等技术的基础上逐步改进。<ref>{{cite web| last=Krauss| first=Kirk J.| title=Matching Wildcards: An Improved Algorithm for Big Data| publisher=Develop for Performance| date=2018| url=http://www.developforperformance.com/MatchingWildcards_AnImprovedAlgorithmForBigData.html}}</ref>

==Tail-recursive functions==

==尾递归函数==

Tail-recursive functions are functions in which all recursive calls are [[tail call]]s and hence do not build up any deferred operations. For example, the gcd function (shown again below) is tail-recursive.  In contrast, the factorial function (also below) is '''not''' tail-recursive; because its recursive call is not in tail position, it builds up deferred multiplication operations that must be performed after the final recursive call completes.  With a [[compiler]] or [[interpreter (computing)|interpreter]] that treats tail-recursive calls as [[goto|jumps]] rather than function calls, a tail-recursive function such as gcd will execute using constant space.  Thus the program is essentially iterative, equivalent to using imperative language control structures like the "for" and "while" loops.

Tail-recursive functions are functions in which all recursive calls are [[tail call]]s and hence do not build up any deferred operations. For example, the gcd function (shown again below) is tail-recursive.  In contrast, the factorial function (also below) is '''not''' tail-recursive; because its recursive call is not in tail position, it builds up deferred multiplication operations that must be performed after the final recursive call completes.  With a [[compiler]] or [[interpreter (computing)|interpreter]] that treats tail-recursive calls as [[goto|jumps]] rather than function calls, a tail-recursive function such as gcd will execute using constant space.  Thus the program is essentially iterative, equivalent to using imperative language control structures like the "for" and "while" loops.

尾部递归函数是指所有递归调用都是尾部调用，因此不建立任何递延操作的函数。例如，gcd函数（如下图所示）是尾递归函数。相反，因子函数（也在下面）不是尾递归的；因为它的递归调用不在尾部位置，所以它建立了递延的乘法运算，这些运算必须在最后的递归调用完成后才能执行。如果编译器或解释器将尾部递归调用视为跳转而非函数调用，那么像gcd这样的尾部递归函数将使用常量空间执行。因此，程序本质上是迭代的，相当于使用 "for "和 "while "循环等命令式语言控制结构。

尾递归函数是指所有递归调用都是尾调用，因此没有任何递延操作的函数。例如，gcd函数（如下图所示）是尾递归函数。相反，阶乘函数（也在下面）不是尾递归的；因为它的递归调用不在尾部位置，所以它存在递延的乘法运算，这些运算必须在最后的递归调用完成后才能执行。如果编译器或解释器将尾部递归调用视为跳转而非函数调用，那么像gcd这样的尾部递归函数将使用常量空间执行。因此，程序本质上是迭代的，相当于使用 "for "和 "while "循环等命令式语言控制结构。

{| class="wikitable"

{| class="wikitable"

       return 1;

       return 1;

   else

   else

       return n * fact(n - 1);

       return fact(n - 1) * n;

}

}

</syntaxhighlight>

</syntaxhighlight>

The significance of tail recursion is that when making a tail-recursive call (or any tail call), the caller's return position need not be saved on the [[call stack]]; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, in languages that recognize this property of tail calls, tail recursion saves both space and time.

The significance of tail recursion is that when making a tail-recursive call (or any tail call), the caller's return position need not be saved on the [[call stack]]; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, in languages that recognize this property of tail calls, tail recursion saves both space and time.

==Order of execution==

==Order of execution==