Python – 54

def R(G,s,A):
    A.add(s)
    for n in set(G[s])-A:R(G,n,A)

R needs to be called with an empty set as an additional argument. This set contains the output, when R has finished. Example of usage:

G = {1: [2, 3], 2: [3], 3: [1], 4:[2]}
A = set()
R(G,1,A)
print A

If you consider this way of output cheating, keep in mind that it’s very normal in C, for example.