1

I know DFS usually can be implemented using recursion function in which system stack is used.

And I know there is Non-recursive Depth-First Search (DFS) Using a Stack.

I wonder every recursion can be called as DFS, if not, is there any example?

VLAZ
  • 26,331
  • 9
  • 49
  • 67
CodingLab
  • 1,441
  • 2
  • 13
  • 37
  • I don't think every recursive function can be said to perform a *search*, so saying it's DFS would certainly be strange. Is a Fibonacci sequence a "search"? How would you do a breadth first search for it? Also, BFS can be implemented recursively, you just need to go around the fact that the call *stack* is a stack and stacks are used in DFS, while BFS uses a queue. – VLAZ Apr 09 '20 at 07:03
  • @VLAZ I agree with you but I also think there can be controversy, because every recursion including Fibonacci case, it can be translated into vertex and edge which forms Graph. and the Graph will be searched or visited during recursion in DFS fashion although I'm not sure we can call it a 'Search'. – CodingLab Apr 09 '20 at 07:11
  • OK, I think you have a point with representing the problem as a graph. I was thinking of how you'd solve something like `2 + 3` recursively as a graph and yes, it's a DFS when implemented that way because you have `2` as a vertex and then edges for `+1`, `+2`, `+3`, etc. So, `2 + 3` using `sum(x, y) => y != 0 ? sum(x + 1, y - 1) : x` (naive implementation) will traverse a `+1` edge three times. I'm still not totally convinced that every recursion *is* a search, though. I'll need to think about this more, perhaps. – VLAZ Apr 09 '20 at 08:12
  • 1
    If you implement recursive BSF would you consider it DFS ? – c0der Apr 09 '20 at 11:24
  • Certainly not. Binary search is recursive, but it's certainly not depth first. Think of how you search for an item in a balanced binary tree: you examine the nodes top-down. That's much different than an inorder traversal, which is definitely depth first. – Jim Mischel Apr 10 '20 at 14:16

0 Answers0