¿Es esta función recursiva aunque no se llame a sí misma?

from pythonds.basic.stack import Stack rStack = Stack() def toStr(n,base): convertString = "0123456789ABCDEF" while n > 0: if n < base: rStack.push(convertString[n]) else: rStack.push(convertString[n % base]) n = n // base res = "" while not rStack.isEmpty(): res = res + str(rStack.pop()) return res print(toStr(1345,2)) 

Me refiero a este tutorial y también pegué el código anterior. El tutorial dice que la función es recursiva pero no veo una llamada recursiva en ninguna parte, solo un bucle de tiempo. ¿Qué me estoy perdiendo?

Tienes razón en que esta función particular no es recursiva. Sin embargo, el contexto es que en la diapositiva anterior había una función recursiva, y en esta quieren mostrar un vistazo de cómo se comporta internamente. Más tarde dicen:

El ejemplo anterior [es decir, el en cuestión – B] nos da una idea de cómo Python implementa una llamada a función recursiva.

Entonces, sí, el título es engañoso, debería ser más bien Expandir una función recursiva o Imitar el comportamiento de una función recursiva con una stack o algo así.

Se puede decir que esta función emplea un enfoque / estrategia recursiva en algún sentido, para resolver el problema, pero no es recursiva en sí misma.

Un algoritmo recursivo , por definición, es un método en el que la solución a un problema depende de soluciones para casos más pequeños del mismo problema .

Aquí, el problema es convertir un número en una cadena en una notación dada.

El “almacenamiento” de datos de la función realmente tiene este aspecto:

 push(d1) push(d2) ... push(dn-1) push(dn) res+=pop(dn) res+=pop(dn-1) ... res+=pop(d2) res+=pop(d1) 

que es efectivamente:

 def pushpop(): push(dx) pushpop(dx+1...dn) res+=pop(dx) 

Es decir, un paso que procesa una porción específica de datos incluye todos los pasos que procesan el rest de los datos (con cada porción procesada de la misma manera).

Se puede argumentar si la función es recursiva (ya que tienden a aplicar el término a las subrutinas en un sentido más estricto), pero el algoritmo que implementa definitivamente lo es.


Para que sientas mejor la diferencia, aquí hay una solución iterativa para el mismo problema:

 def toStr(n,base): charmap = "0123456789ABCDEF" res='' while n > 0: res = charmap[n % base] + res n = n // base return res 

Como puede ver, este método tiene una huella de memoria mucho menor, ya que no almacena tareas. Esta es la diferencia: un algoritmo iterativo realiza cada paso utilizando la misma instancia del estado mediante la mutación , mientras que uno recursivo crea una nueva instancia para cada paso , almacenándolos necesariamente si los antiguos aún son necesarios.

Porque estás usando una estructura de stack.

Si considera cómo se implementa la llamada de funciones, la recursión es esencialmente una forma fácil de hacer que el comstackdor administre una stack de invocaciones para usted.

Esta función hace todo el manejo de la stack manualmente, pero aún así es conceptualmente una función recursiva, solo una en la que la administración de la stack se realiza manualmente en lugar de dejar que el comstackdor lo haga.