A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. Given a digraph G, a partially complemented digraph (G) over tilde is a digraph obtained from G by performing a sequence of vertex complement operations on G. Dahlhaus et al. showed that, given an adjacency-list representation of (G) over tilde, depth-first search (DFS) on G can be performed in O(n + (m) over tilde) time, where (m) over tilde is the number of vertices and ill is the number of edges in (G) over tilde. This can be used for finding a depth-first spanning forest and the strongly connected components of the complement of G in time that is linear in the size of G, and Dahlhaus et al. give applications to finding the modular decomposition of an undirected graph that require that some adjacency lists be complemented and others not. To achieve this bound, their algorithm makes use of a somewhat complicated stack-like data structure to simulate the recursion stack, instead of implementing it directly as a recursive algorithm. We give a recursive O(n + (m) over tilde) algorithm that requires no such data-structures. (C) 2016 Elsevier B.V. All rights reserved.