We introduce and analyze a task in which a tripartite quantum state is transformed to an approximately recoverable state by a randomizing operation on one of the three subsystems. We consider cases where the initial state is a tensor product of n copies of a tripartite state rho(ABC), and is transformed by a random unitary operation on A(n) to another state, which is approximately recoverable from its reduced state on A(n)B(n) (Case 1) or (BCn)-C-n (Case 2). We analyze the minimum cost of randomness per copy required for the task in an asymptotic limit of infinite copies and vanishingly small error of recovery, mainly focusing on the case of pure states. We prove that the minimum cost in Case 1 is equal to the Markovianizing cost of the state, for which a single-letter formula is known. With an additional requirement on the convergence speed of the recovery error, we prove that the minimum cost in Case 2 is also equal to the Markovianizing cost. Our results have an application for distributed quantum computation.