We study a one-dimensional supercritical branching random walk in a non-i.i.d. random environment, which considers both the branching mechanism and the step transition. This random environment is constructed using a recurrent Markov chain on a finite or countable state space. Criteria of (strong) recurrence and transience are presented for this model.