递归或迭代？ [英] Recursion or Iteration?

问题描述

有没有性能损失，如果我们使用循环而不是递归或反之亦然算法，其中两个可以达到同样的目的？例如：检查是否给定的字符串是回文。 我已经看到了使用递归作为一种手段来炫耀，当一个简单的迭代算法可以配得上很多程序员。 该编译器在决定使用什么样的发挥至关重要的作用？

Is there a performance hit if we use loop instead of recursion or vice versa in algorithms where both can serve the same purpose? Eg : Check if given string is palindrome. I have seen many programmers using recursion as a means to show off when a simple iteration algorithm can fit the bill. Does the compiler play a vital role in deciding what to use?

推荐答案

这是可能的递归会更昂贵，取决于该递归函数的尾递归（最后一行是递归调用）。尾递归的应该的编译器识别和优化，其迭代对应（在保持简洁，清晰的实现你在你的code）。

It is possible that recursion will be more expensive, depending on if the recursive function is tail recursive (last line is recursive call). Tail recursion should be recognized by the compiler and optimized to its iterative counterpart (while maintaining the concise, clear implementation you have in your code).

我会写的算法，其中最有意义和最清晰的穷人吸盘的方式（无论是自己或别人），有保持code在数月或数年。如果您遇到性能问题，那么您的配置文件code，然后才把考虑优化移动了一个迭代实现。你可能想看看记忆化和的动态规划。

I would write the algorithm in the way that makes the most sense and is the most clear for the poor sucker (be it yourself or someone else) that has to maintain the code in a few months or years. If you run into performance issues, then profile your code, and then and only then look into optimizing by moving over to an iterative implementation. You may want to look into memoization and dynamic programming.

这篇关于递归或迭代？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！