递归有哪些优点和缺点？

Question

关于在排序算法中使用非递归方法的递归,或者就此而言,任何算法的优缺点是什么？

Answer 1

在大多数情况下,递归较慢,并且也占用了更多的堆栈.递归的主要优点是,对于像树遍历这样的问题,它使算法更容易或更"优雅".看看一些比较:

链接

Answer 2

递归意味着函数重复调用

它使用系统堆栈来完成它的任务.当堆栈使用LIFO方法时,当一个函数被调用时,被控制被移动到定义函数的位置,该函数被存储在具有某个地址的存储器中,该地址存储在堆栈中

其次,它减少了程序的时间复杂度.

虽然有点偏离主题,但有点相关.必读.:递归与迭代

Answer 3

可以递归地定义所有算法.这使得可视化和证明更加容易.

一些算法(例如,Ackermann函数)不能(容易地)迭代地指定.

如果无法执行尾调用优化,则递归实现将使用比循环更多的内存.虽然迭代可能比无法优化的递归函数使用更少的内存,但它在表达能力方面存在一些限制.

Answer 4

任何使用递归实现的算法也可以使用迭代实现。

为什么不使用递归

1. 由于维护堆栈的开销，它通常较慢。
2. 它通常为堆栈使用更多内存。

为什么要使用递归

1. 递归增加了清晰度并且（有时）减少了编写和调试代码所需的时间（但不一定减少空间需求或执行速度）。
2. 降低时间复杂度。
3. 在解决基于树结构的问题时表现更好。

例如，与迭代相比，使用递归更容易解决河内塔问题。