递归实现会比循环遍历在面试中扣分吗

众所周知在binary search, dp等算法里有递归实现(recursive)和循环遍历(iterative)两种实现方法。像binary search里recursive的空间复杂度为O(log N)而iterative的空间复杂度为O(1)，但个人对于recursive要远比iterative运用的熟练。面试里如果用recursive实现的话会因为空间复杂度不够优化而扣分吗？

简单的可能会被要求iterative实现，典型例子如前中后序的树遍历、bottom-up DP、楼主说的binary search等等。
逻辑复杂的backtracking、图和树的DFS、divide and conquer、quicksort / merge sort等就大胆写recursive吧。你让面试官写iterative他也不一定写得出。
觉得不放心就直接问他是想要recursive还是iterative呗。

maristie 发表于 2021-6-29 03:40
简单的可能会被要求iterative实现，典型例子如前中后序的树遍历、bottom-up DP、楼主说的binary search等等 ...

刚面了家小公司，refresh oa，oa时候dfs写的recursion，面试要求改成iterative，醉了。