Batched network codes are a class of efficient random linear network coding schemes employing an outer-code-inner-code structure. In existing designs of efficient batched network codes, the decoding algorithm is a combination of intra-batch Gaussian elimination and inter-batch belief propagation, a process known as GE-BP decoding. To ensure close-to-optimal performance of GE-BP decoding, a large finite field is usually required in either the outer code or the inner code. However, GE-BP decoding over a large field incurs a high computation cost in both software and hardware implementations. In this paper, we introduce a new decoding algorithm that can achieve both the low computation cost of a binary outer code and a binary inner code, and the close-to-optimal decoding performance. Our algorithm takes advantage of the partial recovery property, which states that even when a system of linear equation has many solutions, certain variables may have a unique solution. This property can substantially improve the decoding performance for coding over the binary field. We provide the design and analysis of the decoding algorithm that employs partial recovery for BATS codes.