Concepto de función recursiva de Python: tutorial de Python para principiantes

En el mundo de la informática, la recursividad se refiere a la técnica de definir una cosa en sus propios términos. En otras palabras, una función recursiva se llama a sí misma para su procesamiento. En este artículo, entenderemos el concepto de función recursiva en Python , un lenguaje de programación muy utilizado en el siglo XXI.

¿Qué es la recursividad de Python ?

En Python, un grupo de declaraciones relacionadas que realizan una tarea específica se denomina "función". Entonces, las funciones dividen su programa en partes más pequeñas. Y es de conocimiento común que una función puede llamar a otras funciones en Python.

Pero algunas otras funciones pueden llamarse a sí mismas. Estas son conocidas como funciones recursivas. Considere dos espejos paralelos colocados uno frente al otro. Ahora bien, cualquier objeto que se mantenga entre los espejos se reflejaría recursivamente.

Entremos en detalles sobre la función recursiva para entender claramente su funcionamiento.

La función recursiva

Sabemos que una función recursiva en Python se llama a sí misma cuando se define a través de expresiones autorreferenciales, es decir, en términos de sí misma. Sigue repitiendo su comportamiento hasta que se cumple una condición particular para devolver un valor o resultado. Veamos ahora un ejemplo para aprender cómo funciona.

Lea también: Preguntas y respuestas de la entrevista de Python

Suponga que desea encontrar el factorial de un número entero. Factorial no es más que el producto de todos los números, a partir de 1 a ese número entero. Por ejemplo, el factorial de 5 (¡escrito como 5!) sería 1*2*3*4*5*6, es decir, 720. Tenemos una función recursiva calc_factorial(x), que se define de la siguiente manera:

def calc_factorial(x):

#Función recursiva para encontrar el factorial de un número entero

si x == 1:

volver 1

demás

devolver (x * calc_factorial(x-1))

¿Qué pasaría si llamas a esta función con un entero positivo como 4? Bueno, cada llamada de función agregará un marco de pila hasta que alcancemos el caso base (cuando el número se reduce a 1). Se requiere la condición base para que la recursión finalice y no continúe indefinidamente. Entonces, en el caso dado, el valor 24 se devolverá después de la cuarta llamada.

Implementación de la función recursiva en Python

Puede haber variadas aplicaciones de funciones recursivas en Python. Por ejemplo, desea hacer un gráfico con un patrón repetido, digamos un copo de nieve de Koch. La recursividad se puede utilizar para generar patrones fractales, que se componen de versiones más pequeñas del mismo diseño.

Otro ejemplo es el de la resolución de juegos. Puede escribir algoritmos recursivos para resolver Sudoku y numerosos juegos complejos. La recursividad se usa más comúnmente en problemas de búsqueda, clasificación y recorrido.

Una característica llamativa de la función es que la implementación recursiva permite retroceder. Entonces, la recursividad se trata de construir una solución de forma incremental y eliminar aquellas soluciones que no satisfacen las restricciones del problema en ninguna etapa. Dos cosas son necesarias para lograr esto: mantener el estado y la estructura de datos adecuada. Siga leyendo para familiarizarse con estos términos.

Leer: Salario de desarrollador de Python en India

mantenimiento del estado

Cada llamada recursiva en Python tiene su propio contexto de ejecución. Al tratar con funciones recursivas en Python, debe enhebrar el estado a través de cada llamada recursiva. Con esto, el estado actual se convierte en parte del contexto de ejecución de la llamada actual. También puede mantener el estado en el ámbito global.

Por ejemplo, si está utilizando la recursividad para calcular 1+2+3+4+…….+10. Aquí, el número actual que está sumando y la suma acumulada hasta ese punto forman el estado que necesita mantener. Mantener el estado implica pasar el estado actual actualizado como argumentos a través de cada llamada. Así es como puedes hacerlo.

def suma_números(número_actual, suma_acumulada)

#Caso base

#Regresar estado final

si el número actual == 11:

devolver la suma_acumulada

#caso recursivo

#Enhebrar el estado a través de una llamada recursiva

Demás:

devuelve suma_números (número_actual + 1, suma_acumulada + número_actual)

Alternativamente, puede usar el estado mutable global. Para mantener el estado con este método, mantenga el estado en el ámbito global.

número_actual = 1

suma_acumulada = 0

def suma_números():

número_actual global

suma_acumulada global

#Caso base

si numero_actual==11

devolver la suma_acumulada

#caso recursivo

demás:

suma_acumulada = suma_acumulada + número_actual

numero_actual = numero_actual + 1

devolver suma_números()

Estructuras de datos recursivas

Una estructura de datos se considera recursiva si se puede definir en términos de versiones más pequeñas y simples de sí misma. Los ejemplos de estructuras de datos recursivas incluyen listas, árboles, estructuras jerárquicas, diccionarios, etc. Una lista puede tener otras listas como elementos. Un árbol tiene subárboles, nodos hoja, etc.

Es importante señalar aquí que la estructura de las funciones recursivas a menudo se modela a partir de las estructuras de datos que toma como entradas. Entonces, las estructuras de datos recursivas y las funciones recursivas van de la mano.

Recursión en el cálculo de Fibonacci

El matemático italiano Fibonacci definió por primera vez los números de Fibonacci en el siglo XIII para modelar el crecimiento de la población de conejos. Dedujo que a partir de una pareja de conejos en el primer año, el número de parejas de conejos nacidos en un año determinado es igual al número de parejas de conejos nacidos en cada uno de los dos últimos años. Esto se puede escribir como: Fn = Fn-1 + Fn-2 (Casos base: F0=1 y F1=1).

Cuando escribe una función recursiva para calcular el número de Fibonacci, puede resultar en una recursividad ingenua. Esto sucede cuando se sigue ingenuamente la definición de la función recursiva y se termina recalculando valores innecesariamente. Para evitar el recálculo, puede aplicar el decorador lru_cache a la función. Almacena en caché los resultados y evita que el proceso se vuelva ineficiente.

Leer más: Las 10 mejores herramientas de Python que todo desarrollador de Python debe conocer

Pros y contras de recursivo

La recursividad ayuda a simplificar una tarea compleja al dividirla en subproblemas. Las funciones recursivas crean un código más limpio y también una generación de secuencias sin complicaciones. Pero la recursividad no viene sin sus limitaciones. A veces, las llamadas pueden resultar costosas e ineficientes, ya que consumen mucho tiempo y memoria. Las funciones recursivas también pueden ser difíciles de depurar.

Terminando

En este artículo, cubrimos el concepto de recursividad de Python , lo demostramos usando algunos ejemplos y también discutimos algunas de sus ventajas y desventajas. ¡Con toda esta información, puede explicar fácilmente las funciones recursivas en su próxima entrevista de Python!

Si tiene curiosidad por aprender sobre ciencia de datos, consulte el Diploma PG en ciencia de datos de IIIT-B y upGrad, creado para profesionales que trabajan y ofrece más de 10 estudios de casos y proyectos, talleres prácticos, tutoría con expertos de la industria, 1- on-1 con mentores de la industria, más de 400 horas de aprendizaje y asistencia laboral con las mejores empresas.