什么是递归算法 尾递归究竟是好是坏？
尾递归究竟是好是坏？
如果递归级别太多，则会出现堆栈溢出异常，因为每次调用都会生成一个新的堆栈帧，并使用此堆栈帧保留当前函数的状态值。如果不需要保存状态值，则可以重用堆栈帧而不会导致堆栈溢出。
以n的阶乘为例：
正常递归：
如果n=3，则每一步都需要保留n值和下一个函数的返回值，因此每次调用都需要创建一个新的堆栈帧
尾部递归：
如果n=3，则每次调用都可以重用堆栈帧，因为不需要保存状态值。
因此，当递归在当前堆栈帧执行后完成时，它不需要保留当前堆栈帧，但根据当前堆栈帧的结果，它可以在进入下一个堆栈帧时优化为尾部递归。通常，尾部递归需要满足递归调用是函数体中最后执行的语句。例如，在factorial示例中，要执行的最后一条语句是直接调用factorial（n-1，n*result），而不是表达式n*factorial（n-1）。如果是表达式，则需要堆栈帧来保留N和阶乘（N-1）的结果。
什么是单向递归，尾递归？言简意赅即可？
尾部递归：程序中只有一个递归语句，它位于末尾。单向递归：指程序中的递归语句，在程序运行之前已经完成，如斐波那契数列。这样，共同的特点是没有分支路由必须以非递归方式保存
当编译器检测到函数调用是尾部递归时，它将覆盖当前活动记录，而不是在堆栈中创建新的活动记录。编译器可以这样做，因为递归调用是当前活动周期中要执行的最后一条语句，因此当调用返回时，堆栈帧中没有其他操作，因此不需要保存堆栈帧。通过覆盖当前堆栈帧而不是在其上添加新的堆栈帧，大大减少了使用的堆栈空间，从而提高了实际操作效率。虽然编译器可以优化尾部递归引起的堆栈溢出，但是在编程中我们应该尽量避免尾部递归，因为所有尾部递归都可以被简单的goto循环所代替。
编译器的任务是什么尾递归优化？
同一语法结构可以层层嵌套，同一结构规则可以重复使用，不会造成结构混乱。用数学术语来说，这是语法结构规则的“递归”。在句法组合中，递归有两种表现形式。一是从最初的结构开始，从头到尾重复相同的语法规则。例如，“computer/I//like”是主谓结构，其谓语（/后半部分）本身是主谓结构。这里，语法规则“主谓”被不间断地使用了两次；另一个表现是相同的语法规则可以在一个结构上每隔一段时间重复使用。例如，在“我/看到///曾///他///写///散文”中，第一层使用“主谓”规则，形成“我/看到他的散文”的主谓结构，第五层再次使用“主谓”规则，形成“他写”的主谓结构。
什么是递归算法 什么是尾递归优化 二叉树的先序遍历非递归算法
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
