«Anda andando» é uma forma perifrástica ou composta em que o verbo andar funciona como auxiliar de si mesmo. É praticamente equivalente a «vai andando» ou «está andando», de acordo com o contexto.

Como se trata de uma expressão em que se repete o mesmo verbo, embora com valores um tanto diferentes, pode-se, mesmo assim, considerar que se verifica um pleonasmo, isto é, uma redundância, pelo que é de evitar, pelo menos, no discurso mais cuidado.