2,443
个编辑
更改
跳到导航
跳到搜索
第1,056行：
第1,056行： − 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. − 第1,086行：
第1,084行： − − 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.
→尾递归函数
==尾递归函数==
==尾递归函数==
尾递归函数是指所有递归调用都是尾调用，因此没有任何递延操作的函数。例如，gcd函数（如下图所示）是尾递归函数。相反，阶乘函数（也在下面）不是尾递归的；因为它的递归调用不在尾部位置，所以它存在递延的乘法运算，这些运算必须在最后的递归调用完成后才能执行。如果编译器或解释器将尾部递归调用视为跳转而非函数调用，那么像gcd这样的尾部递归函数将使用常量空间执行。因此，程序本质上是迭代的，相当于使用 "for "和 "while "循环等命令式语言控制结构。
尾递归函数是指所有递归调用都是尾调用，因此没有任何递延操作的函数。例如，gcd函数（如下图所示）是尾递归函数。相反，阶乘函数（也在下面）不是尾递归的；因为它的递归调用不在尾部位置，所以它存在递延的乘法运算，这些运算必须在最后的递归调用完成后才能执行。如果编译器或解释器将尾部递归调用视为跳转而非函数调用，那么像gcd这样的尾部递归函数将使用常量空间执行。因此，程序本质上是迭代的，相当于使用 "for "和 "while "循环等命令式语言控制结构。
</syntaxhighlight>
</syntaxhighlight>
|}
|}
尾递归的意义在于，当进行尾递归调用（或任何尾调用）时，调用者的返回位置不需要保存在调用栈上，当递归调用返回时，它将直接在先前保存的返回位置上进行分支。因此，在识别尾调用这一特性的语言中，尾部递归既节省了空间又节省了时间。
尾递归的意义在于，当进行尾递归调用（或任何尾调用）时，调用者的返回位置不需要保存在调用栈上，当递归调用返回时，它将直接在先前保存的返回位置上进行分支。因此，在识别尾调用这一特性的语言中，尾部递归既节省了空间又节省了时间。