1. Recursion

To solve this problem, you should find a recursion involving the number of nodes in the graph $\small \texttt{numNodes(node)}$. The total number of nodes in a graph is just the 1 node you're standing at, plus all the nodes in all of the neighbors' graphs. Here's the recursion:

2. Base case

The recursion will enter an infinite loop if there are any cycles in the graph.

To prevent infinite loops, you should keep track of all the nodes you've seen so that you never visit a node twice. If you've already seen a node, you should return 0 to stop the recursion and avoid double counting the node. Here's the base case:

It turns out that when you use graphs, you typically don't need to create a base case for null nodes. This is because function calls to numNodes are made by looping over the neighbors array. If there are no neighbors, numNodes won't be called at all.

3. Code

To code this up, we can combine the recursion and base case. Here's the code:

Time Complexity $O(n)$. We loop through every node in the graph.

Space Complexity $O(n)$. We store all the nodes in a set. We also store the call stack in memory.

To recap, when you deal with graphs you should keep track of the nodes that you've visited to avoid infinite cycles.