递归算法经典实例 尾递归究竟是好是坏？
尾递归究竟是好是坏？
如果递归级别太多，则会出现堆栈溢出异常，因为每次调用都会生成一个新的堆栈帧，并使用此堆栈帧保留当前函数的状态值。如果不需要保存状态值，则可以重用堆栈帧而不会导致堆栈溢出。
以n的阶乘为例：
正常递归：
如果n=3，则每一步都需要保留n值和下一个函数的返回值，因此每次调用都需要创建一个新的堆栈帧
尾部递归：
如果n=3，则每次调用都可以重用堆栈帧，因为不需要保存状态值。
因此，当递归在当前堆栈帧执行后完成时，它不需要保留当前堆栈帧，但根据当前堆栈帧的结果，它可以在进入下一个堆栈帧时优化为尾部递归。通常，尾部递归需要满足递归调用是函数体中最后执行的语句。例如，在factorial示例中，要执行的最后一条语句是直接调用factorial（n-1，n*result），而不是表达式n*factorial（n-1）。如果是表达式，则需要堆栈帧来保留N和阶乘（N-1）的结果。
什么是递归啊？
递归作为一种算法，广泛应用于编程语言中。它是指在运行的程序中直接或间接调用自身的函数/过程/子程序的重入现象。调用自身的编程技巧称为递归。过程或函数在其定义或描述中直接或间接地调用自己的方法。它通常将一个庞大而复杂的问题层层转化为一个类似于原始问题的小规模问题来求解。递归策略只需要少量的程序来描述问题求解过程中所需的重复计算，大大减少了代码量。递归的能力是用有限的语句定义一组无限的对象。用递归方法编写的程序简单易懂。一般来说，递归需要边界条件、递归前向段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。注：（1）递归是在过程或函数中调用自身。（2） 在使用增量约简策略时，必须有一个显式的递归结束条件，称为递归退出。
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
