Link Search Menu Expand Document

Recursividad

驴En qu茅 trabajas? Estoy intentando arreglar los problemas que cre茅 cuando intentaba arreglar los problemas que cre茅 cuando intentaba arreglar los problemas que cre茅. Y as铆 naci贸 la recursividad.

La recursividad o recursi贸n es un concepto que proviene de las matem谩ticas, y que aplicado al mundo de la programaci贸n nos permite resolver problemas o tareas donde las mismas pueden ser divididas en subtareas cuya funcionalidad es la misma. Dado que los subproblemas a resolver son de la misma naturaleza, se puede usar la misma funci贸n para resolverlos. Dicho de otra manera, una funci贸n recursiva es aquella que est谩 definida en funci贸n de s铆 misma, por lo que se llama repetidamente a s铆 misma hasta llegar a un punto de salida.

Cualquier funci贸n recursiva tiene dos secciones de c贸digo claramente divididas:

  • Por un lado tenemos la secci贸n en la que la funci贸n se llama a s铆 misma.
  • Por otro lado, tiene que existir siempre una condici贸n en la que la funci贸n retorna sin volver a llamarse. Es muy importante porque de lo contrario, la funci贸n se llamar铆a de manera indefinida.

Veamos unos ejemplos con el factorial y la serie de fibonacci.

Calcular factorial

Uno de los ejemplos mas usados para entender la recursividad, es el c谩lculo del factorial de un n煤mero n!. El factorial de un n煤mero n se define como la multiplicaci贸n de todos sus n煤meros predecesores hasta llegar a uno. Por lo tanto 5!, le铆do como cinco factorial, ser铆a 5*4*3*2*1.

Utilizando un enfoque tradicional no recursivo, podr铆amos calcular el factorial de la siguiente manera.

def factorial_normal(n):
    r = 1
    i = 2
    while i <= n:
        r *= i
        i += 1
    return r

factorial_normal(5) # 120

Dado que el factorial es una tarea que puede ser dividida en subtareas del mismo tipo (multiplicaciones), podemos darle un enfoque recursivo y escribir la funci贸n de otra manera.

def factorial_recursivo(n):
    if n == 1:
        return 1
    else:
        return n * factorial_recursivo(n-1)

factorial_recursivo(5) # 120

Lo que realmente hacemos con el c贸digo anterior es llamar a la funci贸n factorial_recursivo() m煤ltiples veces. Es decir, 5! es igual a 5 * 4! y 4! es igual a 4 * 3! y as铆 sucesivamente hasta llegar a 1.

Algo muy importante a tener en cuenta es que si realizamos demasiadas llamadas a la funci贸n, podr铆amos llegar a tener un error del tipo RecursionError. Esto se debe a que todas las llamadas van apil谩ndose y creando un contexto de ejecuci贸n, algo que podr铆a llegar a causar un stack overflow. Es por eso por lo que Python lanza ese error, para protegernos de llegar a ese punto.

Serie de Fibonacci

Otro ejemplo muy usado para ilustrar las posibilidades de la recursividad, es calcular la serie de fibonacci. Dicha serie calcula el elemento n sumando los dos anteriores n-1 + n-2. Se asume que los dos primeros elementos son 0 y 1.

def fibonacci_recursivo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursivo(n-1) + fibonacci_recursivo(n-2)

Podemos ver que siempre que la n sea distinta de cero o uno, se llamar谩 recursivamente a la funci贸n, buscando los dos elementos anteriores. Cuando la n valga cero o uno se dejar谩 de llamar a la funci贸n y se devolver谩 un valor concreto. Podemos calcular el elemento 7, que ser谩 0,1,1,2,3,5,8,13, es decir, 13.

fibonacci_recursivo(7)
# 13