Recursion that never bottoms out

Two functions from a code review. count_nodes should count reachable nodes in an undirected graph given as an adjacency list; sum_digits should add the decimal digits of a non-negative integer. Both crash with RecursionError: maximum recursion depth exceeded on ordinary inputs. Find the cause of each.

1def count_nodes(adj, u):
2    total = 1
3    for v in adj[u]:
4        total += count_nodes(adj, v)
5    return total
6 
7 
8def sum_digits(n):
9    if n == 1:
10        return 1
11    return n % 10 + sum_digits(n // 10)
12 
13print(count_nodes({0: [1], 1: [0, 2], 2: [1]}, 0))
14print(sum_digits(20))

1. For each function, identify the missing or wrong termination condition.
2. Trace count_nodes on the three-node path graph for two or three calls to show the cycle of calls.
3. Trace sum_digits(20) and show why it never hits the base case. Why does sum_digits(120) happen to work?
4. Fix both. For count_nodes, explain what the visited set represents and whether it should be a parameter or a closure.
5. State the recursion depth each fixed function can reach and what to do if that is too deep.