Inductive Logic Programming systems that handle recursion and predicate invention (PI) generally have limited scalability. A problem is that they search program spaces syntactically, which cannot be effectively guided by utilizing data relations. We propose to restrict the Datalog language to allow a constructive approach to synthesize programs with recursive PI. The learning procedure consists of incremental generalization steps that monotonically explain more examples with new rules. The generalization consists of four steps: Deduction, Abduction, Sampling, and Triangulation (DAST). The deduction and abduction extend background knowledge and unexplained examples to allow for creating recursive rules with invented predicates. The sampling and triangulation perform random walks on deduced and abduced atoms and fold the sampled long rules into many short rules to invent predicates. We implemented DAST with beam search and tested it on various learning tasks. The proposed method shows scalability advantages, especially on tasks that require PI and recursion. Our method synthesizes list reversal, which we believe was unsolved before without any learning bias.