0

What's the difference between using Recursion and stack to implement DFS? probably from the perspective of running time or cache usage Which one is better?

Thank you!

using stack will spend less time and be more cache-friendly?

qbb
  • 1
  • 1
  • 2
    Recursive calls are actually handled by the compiler/interpreter by using a stack!! So conceptually, the two options are the same. However, if you make up your own stack, you can decide to put exactly the information you're interested in in that stack, rather than all the information related to function calls that the compiler would put in there. Also, your program has access to two kinds of memories, titled "the stack" and "the heap". When you allocate your own data structure, such as a stack, it goes to the heap. When you make a recursive call, it goes to the stack. – Stef Mar 23 '22 at 10:34
  • 1
    Similar question: [Depth-first-search: stack or recursion?](https://stackoverflow.com/questions/59171512/depth-first-search-stack-or-recursion) – Stef Mar 23 '22 at 10:36
  • 1
    Related: [What and where are the stack and heap?](https://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap) – Stef Mar 23 '22 at 10:36
  • As for the particulars of whether defining your own stack will be more or less efficient than using recursion, that depends strongly on the language. In python, yes, you absolutely should use a stack and avoid recursion. In haskell, no, using recursion is probably the better way. – Stef Mar 23 '22 at 10:39
  • Does this answer your question? [Depth-First-Search (Stack or Recursion?)](https://stackoverflow.com/questions/59171512/depth-first-search-stack-or-recursion) – ggorlen Mar 25 '22 at 14:09
  • See also [which is faster?](https://ericlippert.com/2012/12/17/performance-rant/) – ggorlen Mar 25 '22 at 14:09

0 Answers0