Tiene la misma complejidad que algoritmo iterativo ya que usa recursion simple.
Puedes usar el
Master theorem para obtener la complejidad de un algoritmo recursivo.
En este caso pasar BFS de iterativo a recursivo es el peor ejemplo que tu maestro te pudo haber puesto. Por que realmente no hay recursion significativa.
Un ejercicio como pasar de:
A una función recursiva tiene el mismo valor que tu ejercicio.
Algunos ejercicios que te pueden servir:
1. Factoriales (recursiva e iterativa)
2. Números de fibonacci (recursiva e iterativa)
3. Dado un numero imprime (por ejemplo 5) imprime: 123454321 (recursiva e iterativa)