Concepto de recursión

1.1 Definición de recursión y sus conceptos básicos.

La recursión es cuando algo se llama a sí mismo una y otra vez. Imagina que tienes una instrucción, y parte de esa instrucción dice seguir la misma instrucción. Es como si dieras la orden de repetir la misma orden.

Ejemplos del mundo real:

Espejos uno frente al otro:

Imagínate que estás entre dos espejos. Ves tu reflejo, y en el reflejo también ves tu reflejo, y así sigue una y otra vez. Este es un ejemplo de recursión, porque cada espejo muestra el reflejo del otro espejo.

Matrioskas:

Una matrioska es una muñeca que tiene otra muñeca dentro, y dentro de esta hay otra, y así sucesivamente. Cuando llegas a la muñeca más pequeña, ya no hay nada más que abrir. Esto es como un caso base en la recursión — el momento para detenerse.

Dividiendo una pizza:

Imagina que estás dividiendo una pizza a la mitad. Luego tomas una de las mitades y la divides a la mitad de nuevo, y así continúas hasta que las porciones son demasiado pequeñas para dividir. Dividir en partes es un proceso recursivo, y el momento en que ya no puedes dividir más es el caso base.

¡Importante! La recursión no es una repetición infinita de comandos, se trata más bien de dividir una tarea compleja en partes, y el enfoque para resolver partes de la tarea es similar a resolver la tarea completa.

¿Cómo funciona esto?

Para entender la recursión, necesitas conocer dos conceptos básicos:

• Caso base: esta es la condición en la que la recursión se detiene. Por ejemplo, en el ejemplo de las matrioskas, el caso base es cuando abres la muñeca más pequeña y ya no hay nada dentro.
• Caso recursivo: es cuando la tarea se repite con partes más pequeñas. En el ejemplo de la pizza, divides el trozo y luego divides la mitad, y así sucesivamente.

¿Por qué es útil?

La recursión ayuda a resolver problemas complejos dividiéndolos en partes más simples. En lugar de resolver toda la tarea de una vez, la resuelves por partes.

Otros ejemplos de la vida:

Cuento dentro de un cuento:

Imagina que un personaje de un cuento cuenta otro cuento, y el personaje de ese cuento comienza a contar otro cuento. Cuando uno de los cuentos termina, regresas al cuento anterior. El caso base es cuando el último cuento termina.

Dibujo recursivo:

Dibujas un triángulo grande, y luego en cada esquina de ese triángulo dibujas un triángulo pequeño, y así continúas hasta que los triángulos se vuelven demasiado pequeños. El caso base es cuando el triángulo se vuelve tan pequeño que ya no se puede dibujar.

1.2 Caso base: definición y ejemplos.

Caso base — es la condición que detiene las llamadas recursivas y permite que la función devuelva un valor específico. Generalmente, es la solución más simple y obvia al problema, que no requiere más recursión.

Ejemplos de caso base:

Factorial de un número:

El factorial de un número n se denota como F(n) == 1 * 2 * 3 * … * n. También es evidente que F(n) == n * F(n - 1).

Caso base: el factorial del número 0 o 1 es igual a 1. F(0) == F(1)==1

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Caso base
    else:
        return n * factorial(n - 1)
        

Números de Fibonacci:

Los números de Fibonacci son una secuencia: 1, 1, 2, 3, 5, 8, 13, … donde cada número siguiente es la suma de los dos anteriores. Para F(n) == F(n-1) + F(n-2)

Caso base: los primeros dos números de Fibonacci son 1, por lo que el "cero" de Fibonacci es igual a 0. O F(0) = 0 y F(1) = 1.

def fibonacci(n):
    if n == 0:
        return 0  # Caso base
    elif n == 1:
        return 1  # Caso base
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 Caso recursivo: definición y ejemplos

Caso recursivo — es la parte de la función que resuelve la tarea llamándose a sí misma con nuevos parámetros que acercan la solución al caso base. Cada llamada recursiva disminuye o modifica la tarea para finalmente alcanzar el caso base.

Ejemplos de caso recursivo:

Factorial de un número:

Caso recursivo: el factorial del número n es n multiplicado por el factorial del número n-1.

def factorial(n):
    if n == 0 or n == 1:
        return 1  # Caso base
    else:
        return n * factorial(n - 1)  # Caso recursivo
        

Números de Fibonacci:

Caso recursivo: F(n) es la suma de F(n-1) y F(n-2).

def fibonacci(n):
    if n == 0:
        return 0  # Caso base
    elif n == 1:
        return 1  # Caso base
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Caso recursivo
        

1.4 Ejemplos de algoritmos recursivos

1. Recorrido de un árbol binario:

Ejemplo de recorrido en "in-order".

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# Ejemplo de uso:
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. Búsqueda del elemento máximo en una lista:

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # Caso base
    else:
        max_of_rest = find_max(lst[1:])  # Caso recursivo
        return max(lst[0], max_of_rest)
        
# Ejemplo de uso:
print(find_max([1, 5, 3, 9, 2]))  # Salida: 9
        
        

3. Búsqueda binaria recursiva:

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # Caso base: elemento no encontrado
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # Caso base: elemento encontrado
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # Caso recursivo
    else:
        return binary_search(arr, target, left, mid - 1)  # Caso recursivo 
# Ejemplo de uso:
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # Salida: 4