Recursividad - Recursion

¿Qué es la recursividad?

Es una técnica donde una función se llama a sí misma para resolver un problema.

La idea clave es esta:

Un problema grande se resuelve dividiéndolo en subproblemas más chicos del mismo tipo.

Ejemplo:

Para calcular factorial(5):
- Necesito factorial(4)
  - Necesito factorial(3)
    - Hasta llegar a un caso simple que se resolver directo.

Las 2 partes OBLIGATORIAS de toda función recursiva

Caso base:

Es la condición de corte.
El caso más simple del problema, que NO hace más llamadas recursivas.

Caso recursivo:

Es donde la función se llama a sí misma, pero con un problema más chico.
IMPORTANTE:Cada llamada recursiva debe acercarse al caso base.

¿Para qué se usa?

Cuando el problema tiene estructura naturalmente recursiva, por ejemplo:

Definiciones matemáticas:

Factorial
Potencia
Fibonacci

Estructuras de datos:

Árboles-Tree
Listas enlazadas-Linked list

Algoritmos clásicos:

Búsqueda binaria
Quicksort
Mergesort

Procesar cosas "anidadas":

Directorios
Expresiones matemáticas
Paréntesis

IMPORTANTE:

No todo lo recursivo es mejor que lo iterativo. En C muchas veces el for o while es:

Más rápido
Más eficiente en memoria

Pero la recursividad:

Es más clara
Expresa mejor la idea del problema

¿Tiene alguna sintaxis especial?

No, la recursividad no tiene sintaxis propia en C.

Es una función común, la única diferencia es que:

Dentro de su cuerpo se llama a sí misma.

Tipos de recursividad:

Recursividad directa
Recursividad indirecta
Recursividad lineal
Recursividad múltiple

Directa:

Una función se llama a sí misma directamente.


void f(...)
{
    /*...*/
    f(...);
}

Ejemplos:

Factorial
Suma
Fibonacci
Recursividad con arrays

Indirecta:

Una función NO se llama a sí misma, sino que llama a otra, que eventualmente vuelve a llamar a la primera.


void A(int n);
{
    if (n > 0)
        B(n - 1);
}
void B(int n)
{
    if (n > 0)
        A(n -1);
}

Llamadas: A → B → A → A → B → ...

Esto casi no se usa en C inicial.

Ejemplos:

Análisis sintáctico
Autómatas
Estados

Recursividad lineal

En cada llamada:

La función hace una sola llamada recursiva.


int f(n)
{
    return algo + f(n - 1);
}

Cómo sucede en:

Factorial
Suma
Recursividad con arrays.

Son fáciles de razonar y convertir en iterativas.

Profundidad de la recursión

En la recursividad lineal, cada llamada genera una sola llamada recursiva. Esto provoca que la cantidad máxima de llamadas activas al mismo tiempo en la pila (stack) sea proporcional al tamaño del problema.

Por eso se dice que la profundidad de la recursión es O(n): si n crece, la cantidad de llamadas en la pila crece de forma lineal.

Recursividad múltiple

En una llamada:

Se hacen 2 o más llamadas recursivas.


int f(n)
{
    return f(n - 1) + f(n - 2);
}

Como sucede en:

Fibonacci

Son muy ineficientes, explosión de llamadas (Se llama 2 o más veces en una llamada. Existiendo una duplicación de subproblemas), crecimiento exponencial.

Ejemplo Clásico de Recursividad 1:

Factorial:


n! = n * (n - 1)!
0! = 1

¿Qué pasa internamente con factorial(5)?

Fase de llamadas (expansión de la expresión):


factorial(5)
-> 5 * factorial(4)
-> 5 * (4 * factorial(3))
-> 5 * (4 * (3 * factorial(2)))
-> 5 * (4 * (3 * (2 * factorial(1))))
-> 5 * (4 * (3 * (2 * (1 * factorial(0)))))
Caso base:
-> factorial(0) = 1 // Caso base, ya no se llama asi mismo

Sustitución y evaluación:
-> 5 * (4 * (3 * (2 * (1 * 1))))
-> 5 * (4 * (3 * (2 * 1)))
-> 5 * (4 * (3 * 2))
-> 5 * (4 * 6)
-> 5 * 24
-> 120

Una vez alcanzado el caso base, las llamadas retornan en orden inverso al que fueron realizadas, liberándose los marcos de activacion de la pila-stack.

La pila (stack): Concepto clave

Cada llamada a función:

Guarda parámetros.
Variables locales.
Dirección de retorno.

Esto va a la pila de ejecución. En recursividad:

Cada llamada ocupa un nuevo "nivel" en la pila.
Demasiadas llamadas => stack overflow

Por eso:

SIEMPRE debe haber CASO BASE.
Y la dimensión del problema debe reducirse.

Ejemplo Clásico de Recursividad 2:

Suma de los primeros N números:


suma(n) = n + suma(n - 1)
suma(0) = 0
int suma(int n)
{
  if (n == 0) // Caso base
      return 0;
  else
      return n + suma(n - 1);
}

Esto es recursivo por definicion, pero ...

Versión iterativa:


int suma(int n)
{
  int total = 0;
  for (int i = 1; i <= n; i++)
      total += i;
  return total;
}

Acá se ve claro:

Recursiva: más "elegante".
Iterativa: más eficiente.

Ejemplo Clásico de Recursividad 3:

Fibonacci:

fib(0) = 0 Caso base.
fib(1) = 1 Caso base.
fib(n) = fib(n -1) + fib(n-2)


int fib(int n)
{
  if (n == 0)
      return 0;
  if (n == 1)
      return 1;
  return fib(n - 1) + fib(n - 2);
}

Este ejemplo es didáctico, pero:

Es muy ineficiente
Repite cálculos
Explota rápido la pila

Ejemplo Clásico de Recursividad 4:

Recursividad con arrays

Imprimir un array recursivamente.


void imprimir(int v[], int n)
{
  if (n == 0) // Caso base
      return;
  imprimir(v, n - 1);
  printf("%d ", v[n - 1]);
}

IMPORTANTE:

La dimensión se reduce (n - 1)
El array no se copia, sólo se pasa la dirección.

Errores típicos:

No tener caso base
Caso base mal definido
No reducir el problema
Confundir retorno con impresión
Creer que es "más mágica" que un bucle(loop)

Consideraciones para resolver ejercicios de recursividad:

Cuando vemos un ejercicio recursivo, preguntarnos:

¿Cuál es el caso base más simple?
¿Cómo expresamos el problema en función del mismo problema más chico?
¿Qué parámetro se achica en cada llamada?

Si no podemos responder esas tres preguntas entonces todavía no es recursivo.

La recursividad es más relevante en:

Listas enlazadas - Linked list
Árboles - Tree
Backtracking

Teoría aplicada:

Makefile


CC = gcc
CFLAGS = -std=c11 -Wall -Wextra -pedantic

PROG = recursividad
OBJ = main.o

$(PROG): $(OBJ)
	$(CC) $(OBJ) -o $(PROG)

$(OBJ): main.c
	$(CC) $(CFLAGS) -c main.c

.PHONY: clean
clean:
	del $(OBJ) $(PROG).exe

Código:


// gcc -std=c11 -Wall -Wextra -pedantic main.c -o recursividad

#include <stdio.h>

/* ---- FACTORIAL ---- */
int factorial(int n)
{
    if (n == 0) // Caso base
        return 1;
    else
        return n * factorial(n - 1); // Caso recursivo
}

/* ---- SUMA ---- */
int suma(int n)
{
    if (n == 0) // Caso base
        return 0;
    else
        return n + suma(n - 1); // Caso recursivo
}

/* ---- FIBONACCI ---- */
int fib(int n)
{
    if (n == 0) // Caso base
        return 0;
    if (n == 1)
        return 1; // Caso base
    return fib(n - 1) + fib(n - 2); // Caso recursivo
}

/* ---- RECURSIVIDAD CON ARRAYS ---- */
void imprimir(int v[], int n)
{
    if (n == 0) // Caso base
        return;
    imprimir(v, n -1); // Caso recursivo
    printf("%d ", v[n -1]);
}

int main(void)
{
    /* ---- FACTORIAL ---- */
    int n = 5;
    printf("Factorial de %d = %d\n", n, factorial(n));

    /* ---- SUMA ---- */
    printf("Suma de los primeros %d numeros = %d\n", n, suma(n));

    /* ---- RECURSIVIDAD CON ARRAYS ---- */
    int v[]= {1, 2, 3, 4, 5};
    imprimir(v, 5);

    return 0;
}

Ejercicios de Recursividad