栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

如何识别什么是尾递归?

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

如何识别什么是尾递归?

它可能会帮助您从实际实现尾部呼叫优化的角度来考虑这一点。当然,这不是定义的一部分,但确实可以激发定义。

通常,在调用函数时,调用代码会将以后需要的所有寄存器值存储在堆栈中。它还将存储一个返回地址,指示调用后的下一条指令。它会做任何需要做的事情,以确保为被调用者正确设置了堆栈指针。然后它将跳转到目标地址[*](在这种情况下,是相同的功能)。返回时,它知道返回值在调用约定指定的位置(寄存器或堆栈插槽)。

对于尾部呼叫,呼叫者不执行此操作。它忽略任何寄存器值,因为它知道以后将不需要它们。它设置了堆栈指针,以便被调用者将使用与调用者相同的堆栈,并且不将自身设置为返回地址,它只是跳转到目标地址。因此,被调用方将覆盖相同的堆栈区域,将其返回值放在调用方应将其返回值放在的相同位置,并且当它返回时,将不返回到其调用方,而是返回到其调用方的呼叫者。

因此,非正式地,当可能进行尾部调用优化时,并且当尾部调用的目标是函数本身时,该函数是尾部递归的。效果与该函数包含一个循环大致相同,并且tail调用跳转到循环的开始,而不是调用自身。这意味着在调用之后必须没有任何变量(实际上也不需要“要做的工作”,在C
++等语言中,这意味着什么都不会被破坏),并且尾调用的返回值必须由调用者返回。

这都是为了简单/平凡的尾递归。有一些转换可用于制作尚未实现的尾部递归,例如,引入额外的参数,存储一些“最底层”递归级别使用的信息,以完成其他工作。出路”。因此,例如:

int triangle(int n) {    if (n == 0) return 0;    return n + triangle(n-1);}

可以由程序员或足够聪明的编译器自动设置为尾递归,如下所示:

int triangle(int n, int accumulator = 0) {    if (n == 0) return accumulator;    return triangle(n-1, accumulator + n);}

因此,正在谈论足够聪明的语言/编译器的人可能会将前一个功能描述为“尾递归”。为该变体用法做好准备。

[*]存储返回地址,移动堆栈指针并跳转,可能会也可能不会被体系结构包装在单个操作码中,但是即使这样通常也不会发生。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/418995.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号