"Depth First Search" equivalence with "recursion tree"

Question

I know that we can see the execution of a recursion function as a recursion tree.

My question is why can we see this execution as a tree?

I think there's a link with the Depth First Search method which uses a stack as the stack used during recursion, but i don't know if there exist of proof of this equivalence.

Do anyone have the answer?

Answer 1

You can think of recursion as a tree. Each recursive call is a node in the tree, and there's an edge from each recursive call instance to each of the calls it fired off.

Since DFS is recursive, you can visualize the call tree for DFS using this manner, but aside from that there isn't much of a direct connection between the two.