精华内容
下载资源
问答
  • 尾递归

    2021-03-13 18:26:11
    当递归调用是方法中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归尾递归的特点是在返回时直接传回原始的调用者,而不用经过中间的调用者,这个特点很重要,因为大多数现代的编译器...
    递归的优点

       递归的优点是代码简洁且易于理解。如果问题满足递归的特点,即可以分解成子问题且子问题与原始问题相似,则可以使用递归给出自然、直接、简单的解法。

    递归的缺点

       时间和空间的消耗比较大。每一次函数调用都需要在内存栈中分配空间,对栈的操作还需要时间,因此时间复杂度和空间复杂度都会比较高。
       如果子问题之间存在重叠,则在不加记忆化的情况下,递归会产生重复计算,导致时间复杂度过高。
       由于栈的空间有限,如果递归调用的次数太多,则可能导致调用栈溢出。

    尾递归

       当递归调用是方法中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。
       尾递归的特点是在返回时直接传回原始的调用者,而不用经过中间的调用者,这个特点很重要,因为大多数现代的编译器会利用该特点自动生成优化的代码。
       使用尾递归代替普通的递归,可以在时间和空间方面都带来显著的提升。

    普通递归代码示例
    在这里插入图片描述
    下面是 msvc 编译器的输出(Og):
    在这里插入图片描述
    尾递归代码示例
    在这里插入图片描述

    下面是 msvc 编译器的输出(Og):
    在这里插入图片描述
    明显,尾递归的汇编代码中没有 call 语句而是转为了循环,这样达到节省栈空间的目的,减小 overhead。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,632
精华内容 1,852
关键字:

尾递归