递归还是迭代? [英] Recursion or Iteration?

问题描述

如果我们在算法中使用循环而不是递归，反之亦然，在两者可以达到相同目的的情况下，性能是否会受到影响?例如:检查给定的字符串是否是回文.我见过许多程序员使用递归来炫耀什么时候简单的迭代算法可以满足要求.编译器在决定使用什么方面起着至关重要的作用吗?

Is there a performance hit if we use a loop instead of recursion or vice versa in algorithms where both can serve the same purpose? Eg: Check if the given string is a 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?

推荐答案

递归可能会更昂贵，这取决于递归函数是否为 尾递归(最后一行是递归调用).尾递归应该被编译器识别并优化为其迭代对应物(同时保持代码中的简洁、清晰的实现).

It is possible that recursion will be more expensive, depending on if the recursive function is tail recursive (the 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).

对于必须在几个月或几年内维护代码的可怜的傻瓜(无论是你自己还是其他人)，我会以最有意义和最清晰的方式编写算法.如果您遇到性能问题，请分析您的代码，然后才通过转向迭代实现来研究优化.您可能需要查看 memoization 和 动态编程.

I would write the algorithm in the way that makes the most sense and is the clearest 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屋！