显式堆栈比递归好吗
Is explicit stack better than recursion
我们可以使用堆栈以及使用递归以相反的顺序打印链表。我的老师说使用显式堆栈更好，因为递归也使用堆栈但必须维护许多其他参数。即使我们从stack使用std::stack，引用外部库不也很耗时吗？与使用递归解决方案相比，使用显式堆栈如何节省 time/space？
递归涉及隐式堆栈的使用。这是由用于编译代码的编译器在后台实现的。
编译器创建的这个后台堆栈称为“调用堆栈”。可以使用堆栈数据结构来实现调用堆栈，该结构存储有关计算机程序的活动子例程的信息。
每个子例程调用都使用调用堆栈中称为堆栈帧的帧。当一个函数 return 有一个值时，它的堆栈帧就会从调用堆栈中弹出。
递归的调用堆栈与显式调用堆栈？
堆栈溢出
2个栈的根本区别在于编译器分配给程序调用栈的space是固定的。这意味着如果您不确定最大编号，将会出现堆栈溢出。预期的递归函数调用数量，并且在给定时间点分配给堆栈的 space 调用数量太多。
另一方面，如果您定义一个显式堆栈，它会在编译器在 运行 时分配给程序的堆 space 上实现。你猜怎么着，堆大小不是固定的，可以在需要时在 run-time 期间动态增加。您真的不必担心显式堆栈溢出。
Space 和时间
对于给定的情况，哪个更快？
在不支持递归相关优化（例如尾递归的尾调用优化）的语言中，在显式堆栈上迭代比递归更快。
什么是尾递归？
尾递归是递归的一种特殊情况，其中递归函数在递归函数调用后不再进行任何计算，即函数的最后一步是对递归函数的调用。
什么是 Tail-call 优化 (TCO)？
Tail-call 优化是您可以避免为函数分配新堆栈帧的地方，因为调用函数只会 return 它从被调用函数获得的值。
因此，支持 tail-call 优化的 compilers/languages 实现了对递归函数的调用，调用堆栈中只有一个堆栈帧。如果您的 compiler/language 不支持此功能，那么使用显式堆栈将为您节省大量 space 和时间。
Python不支持尾调用优化。这样做的主要原因是要有一个完整而清晰的堆栈跟踪，从而可以进行高效的调试。几乎所有 C/C++ 编译器都支持尾调用优化。
有时，显式控制堆栈有助于在使用多个参数时简化事情。
而递归解决方案使源代码的大小更小且更易于维护。
结论
说到底，没有固定的答案。对于特定场景，需要考虑很多因素，比如可扩展性、代码可维护性、language/compiler被使用等。
最好的方法是使用两种方式实施解决方案，在输入集上对 2 个解决方案进行计时，并在将其部署到生产设置之前分析峰值 space 利用率。
我们可以使用堆栈以及使用递归以相反的顺序打印链表。我的老师说使用显式堆栈更好，因为递归也使用堆栈但必须维护许多其他参数。即使我们从stack使用std::stack，引用外部库不也很耗时吗？与使用递归解决方案相比，使用显式堆栈如何节省 time/space？
递归涉及隐式堆栈的使用。这是由用于编译代码的编译器在后台实现的。 编译器创建的这个后台堆栈称为“调用堆栈”。可以使用堆栈数据结构来实现调用堆栈，该结构存储有关计算机程序的活动子例程的信息。
每个子例程调用都使用调用堆栈中称为堆栈帧的帧。当一个函数 return 有一个值时，它的堆栈帧就会从调用堆栈中弹出。
递归的调用堆栈与显式调用堆栈？
堆栈溢出
2个栈的根本区别在于编译器分配给程序调用栈的space是固定的。这意味着如果您不确定最大编号，将会出现堆栈溢出。预期的递归函数调用数量，并且在给定时间点分配给堆栈的 space 调用数量太多。 另一方面，如果您定义一个显式堆栈，它会在编译器在 运行 时分配给程序的堆 space 上实现。你猜怎么着，堆大小不是固定的，可以在需要时在 run-time 期间动态增加。您真的不必担心显式堆栈溢出。
Space 和时间
对于给定的情况，哪个更快？ 在不支持递归相关优化（例如尾递归的尾调用优化）的语言中，在显式堆栈上迭代比递归更快。
什么是尾递归？
尾递归是递归的一种特殊情况，其中递归函数在递归函数调用后不再进行任何计算，即函数的最后一步是对递归函数的调用。
什么是 Tail-call 优化 (TCO)？
Tail-call 优化是您可以避免为函数分配新堆栈帧的地方，因为调用函数只会 return 它从被调用函数获得的值。
因此，支持 tail-call 优化的 compilers/languages 实现了对递归函数的调用，调用堆栈中只有一个堆栈帧。如果您的 compiler/language 不支持此功能，那么使用显式堆栈将为您节省大量 space 和时间。
Python不支持尾调用优化。这样做的主要原因是要有一个完整而清晰的堆栈跟踪，从而可以进行高效的调试。几乎所有 C/C++ 编译器都支持尾调用优化。
有时，显式控制堆栈有助于在使用多个参数时简化事情。 而递归解决方案使源代码的大小更小且更易于维护。
结论
说到底，没有固定的答案。对于特定场景，需要考虑很多因素，比如可扩展性、代码可维护性、language/compiler被使用等。 最好的方法是使用两种方式实施解决方案，在输入集上对 2 个解决方案进行计时，并在将其部署到生产设置之前分析峰值 space 利用率。