5.10. Recursividad

La recursividad consiste en resolver un problema a partir de casos más simples del mismo problema. Una función recursiva es aquella que se "llama a ella misma", reduciendo la complejidad paso a paso hasta llegar a un caso trivial.

Dentro de las matemáticas tenemos varios ejemplos de funciones recursivas. Uno clásico es el "factorial de un número":

El factorial de 1 es 1:

1! = 1

Y el factorial de un número arbitrario es el producto de ese número por los que le siguen, hasta llegar a uno:

n! = n · (n-1) · (n-2) · ... · 3 · 2 · 1

(por ejemplo, el factorial de 4 es 4 • 3 • 2 • 1 = 24)

Si pensamos que el factorial de n-1 es

(n-1)! = (n-1) · (n-2) · (n-3) · ... · 3 · 2 · 1

Entonces podemos escribir el factorial de un número a partir del factorial del siguiente número:

n! = n · (n-1)!

Esta es la definición recursiva del factorial, ni más ni menos. Esto se podría programar así:

// Ejemplo_05_10a.cs
// Funciones recursivas: factorial
// Introducción a C#, por Nacho Cabanes

using System;

public class Ejemplo_05_10a
{

    public static long Factorial(int n) 
    {
        if (n==1)               // Aseguramos que termine (caso base)
            return 1;
        return n * Factorial(n-1);  // Si no es 1, sigue la recursión
    }

    public static void Main()
    {
        int num;
        Console.WriteLine("Introduzca un número entero: ");
        num = Convert.ToInt32(System.Console.ReadLine()); 
        Console.WriteLine("Su factorial es: {0}", Factorial(num));
    }
  
}

Dos consideraciones importantes:

• Atención a la primera parte de la función recursiva: es muy importante comprobar que hay salida de la función, para que nuestro programa no se quede dando vueltas todo el tiempo y deje el ordenador (o la tarea actual) "colgado". Debemos encontrar un "caso trivial" que alcanzar, y un modo de disminuir la complejidad del problema acercándolo a ese caso.
• Los factoriales crecen rápidamente, así que no conviene poner números grandes: el factorial de 16 es 2.004.189.184, luego a partir de 17 podemos obtener resultados erróneos, si usamos números enteros "normales".

¿Qué utilidad tiene esto? Más de la que parece: muchos problemas complicados se pueden expresar a partir de otro más sencillo. En muchos de esos casos, ese problema se podrá expresar de forma recursiva. Los ejercicios propuestos te ayudarán a descubrir otros ejemplos de situaciones en las que se puede aplicar la recursividad.

Ejercicios propuestos:

Ejercicio propuesto 5.10.1: Crea una función que calcule el valor de elevar un número entero a otro número entero (por ejemplo, 5 elevado a 3 = 53 = 5 • 5 • 5 = 125). Esta función se debe crear de forma recursiva. Piensa cuál será el caso base (qué potencia se puede calcular de forma trivial) y cómo pasar del caso "n-1" al caso "n" (por ejemplo, si sabes el valor de 5⁴, cómo hallarías el de 5⁵ a partir de él).

Ejercicio propuesto 5.10.2: Como alternativa, crea una función que calcule el valor de elevar un número entero a otro número entero de forma NO recursiva (lo que llamaremos "de forma iterativa"), usando la orden "for".

Ejercicio propuesto 5.10.3: Crea un programa que emplee recursividad para calcular un número de la serie Fibonacci (en la que los dos primeros elementos valen 1, y para los restantes, cada elemento es la suma de los dos anteriores).

Ejercicio propuesto 5.10.4: Crea un programa que emplee recursividad para calcular la suma de los elementos de un vector de números enteros, desde su posición inicial a la final, usando una función recursiva que tendrá la apariencia: SumaVector(v, desde, hasta). Nuevamente, piensa cuál será el caso base (cuántos elementos podrías sumar para que dicha suma sea trivial) y cómo pasar del caso "n-1" al caso "n" (por ejemplo, si conoces la suma de los 6 primeros elementos y el valor del séptimo elemento, cómo podrías emplear esta información para conocer la suma de los 7 primeros).

Ejercicio propuesto 5.10.5: Crea un programa que emplee recursividad para calcular el mayor de los elementos de un vector. El planteamiento será muy similar al del ejercicio anterior.

Ejercicio propuesto 5.10.6: Crea un programa que emplee recursividad para dar la vuelta a una cadena de caracteres (por ejemplo, a partir de "Hola" devolvería "aloH"). La función recursiva se llamará "Invertir(cadena)". Como siempre, analiza cuál será el caso base (qué longitud debería tener una cadena para que sea trivial darle la vuelta) y cómo pasar del caso "n-1" al caso "n" (por ejemplo, si ya has invertido las 5 primeras letras, que ocurriría con la de la sexta posición).

Ejercicio propuesto 5.10.7: Crea, tanto de forma recursiva como de forma iterativa, una función diga si una cadena de caracteres es simétrica (un palíndromo). Por ejemplo, "DABALEARROZALAZORRAELABAD" es un palíndromo.

Ejercicio propuesto 5.10.8: Crear un programa que encuentre el máximo común divisor de dos números usando el algoritmo de Euclides: Dados dos números enteros positivos m y n, tal que m > n, para encontrar su máximo común divisor, es decir, el mayor entero positivo que divide a ambos: - Dividir m por n para obtener el resto r (0 ≤ r < n) ; - Si r = 0, el MCD es n.; - Si no, el máximo común divisor es MCD(n,r).

Ejercicio propuesto 5.10.9: Crea dos funciones que sirvan para saber si un cierto texto es subcadena de una cadena. No puedes usar "Contains" ni "IndexOf", sino que debes analizar letra a letra. Una función debe ser iterativa y la otra debe ser recursiva.

Ejercicio propuesto 5.10.10: Crea una función que reciba una cadena de texto, y una subcadena, y devuelva cuántas veces aparece la subcadena en la cadena, como subsecuencia formada a partir de sus letras en orden. Por ejemplo, si recibes la palabra "Hhoola" y la subcadena "hola", la respuesta sería 4, porque se podría tomar la primera H con la primera O (y con la L y con la A), la primera H con la segunda O, la segunda H con la primera O, o bien la segunda H con la segunda O. Si recibes "hobla", la respuesta sería 1. Si recibes "ohla", la respuesta sería 0, porque tras la H no hay ninguna O que permita completar la secuencia en orden.