Abstract In this paper, we propose a new algorithm for computing recursive closures. The main idea behind this algorithm is tree labeling and graph decomposition, based on which the transitive closure of a directed graph can be computed in O(e?d_max?d_out) time and in O(n?d_max?d_out) space, where n is the number of the nodes of the graph, e is the numbers of the edges, d max is the maximal indegree of the nodes, and d_out is the average outdegree of the nodes. Especially, this method can be used to efficiently compute recursive relationships of a directed graph in a relational environment.