High ductility cementitious composite (HDCC) is recognized as an ideal structural bonding and repair material due to multiple steady-state cracking and strain-hardening properties. However, higher shrinkage strains and low economic and environmental friendliness limit its wide application. To promote the application of HDCC, recycled high ductility cementitious composite (R-HDCC) was prepared by using recycled fine aggregate (RFA) to replace natural fine aggregate (NFA), and the effects of RFA substitution rate and fly ash content on the mechanical and shrinkage properties of R-HDCC were thoroughly investigated. The results showed that the compressive strength of R-HDCC gradually decreased with the increase of RFA substitution, but its tensile strain was enhanced. R-HDCC, with 100% RFA substitution, still maintained a tensile strength of 2.66 MPa and a tensile strain capacity of 2.46%. The high fly ash content improved the matrix ductility, resulting in a 54.19% increase in tensile strain over natural HDCC. In addition, the incorporation of RFA and fly ash reduced the autogenous shrinkage of R-HDCC due to the internal curing effect, but the total drying shrinkage of the matrix increased with increasing RFA substitution rate. R100-70 showed optimal environmental benefits and engineering application value through environmental impact assessment and economic analysis. Finally, this paper is expected to guide the design of ecological, economical, and high-performance R-HDCC.