We consider a particle performing a random walk on a Galton–Watson tree, when the probabilities of jumping from a vertex to any one of its neighbours are determined by a random process. We introduce a method for deriving conditions under which the walk is either transient or recurrent. We first suppose that the weights are i.i.d., and re-prove a result of Lyons and Pemantle (Ann. Probab. 20 (1992) 125–136). We then assume a Markovian environment along each line of descent, and finally consider a random walk in a Markovian environment that itself changes the environment. Our approach involves studying the typical behaviour of the walk on fixed lines of descent, which we then show determines the behaviour of the process on the whole tree.