Este sitio web usa cookies de terceros para analizar el tráfico y personalizar los anuncios. Si no está de acuerdo, abandone el sitio y no siga navegando por él. ×


6.5. Recursividad

La idea en sí es muy sencilla: un procedimiento o función es recursivo si se llama a sí mismo.

¿Qué utilidad puede tener eso? Habrá muchos problemas que son más fáciles de resolver si se descomponen en pasos cada vez más sencillos. Y existen otros problemas en los que querremos probar todas las posibles soluciones, para escoger la óptima, y en ciertos casos, la recursividad será casi el único modo de conseguirlo.

Vamos a empezar por ver un ejemplo clásico de función recursiva: el factorial de un número.

Partimos de la definición matemática del factorial de un número entero n:

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

Es decir, el factorial es el resultado de multiplicar ese número por el siguiente número más pequeño (n-1), luego por el siguiente (n-2) y así sucesivamente hasta llegar a 1.

Por otra parte, el factorial del siguiente número más pequeño a éste, (n-1), se puede escribir como

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

Se parecen mucho, de modo que podemos escribir el factorial de un número "n" en función del factorial del siguiente número, "n-1":

n! = n * (n-1)!

Esa es la definición recursiva del factorial: Vamos "delegando" para que el problema lo resuelva el siguiente número, y este a su vez se lo pasa al siguiente, y este al otro, y así sucesivamente hasta llegar a algún caso que sea muy fácil.

Vamos a ver cómo se imitaría esa lógica mediante un programa:

(* FACT.PAS, Factorial, ejemplo de recursividad *)
(* Parte de CUPAS5, por Nacho Cabanes           *)
 
program PruebaDeFactorial;
 
var numero: integer;
 
function factorial( num : integer) : integer;
begin
    if num = 1 then
        factorial := 1    (* Aseguramos que tenga salida (caso base) *)
    else
        factorial := num * factorial( num-1 );       (* Caso general *)
end;
 
begin
    writeLn( 'Introduce un numero entero (no muy grande)  ;-)' );
    readLn(numero);
    writeLn( 'Su factorial es ', factorial(numero) );
end. 
 

Esto es lo que hay que tener presente de este programa:

La recursividad suele ser "difícil de ver" en un principio. Una herramienta que puede ayudar es pensar cómo sería la "traza del programa", que es la secuencia de órdenes que se van a ejecutar y los valores que van a tener las variables a medida que el programa avanza. Vamos a ver cómo sería la traza del programa anterior si es usuario introduce el valor 4:

Primera llamada: factorial( 4 )
num = 1  ? No => devolver 4 * factorial( 3 )
    Segunda llamada: factorial( 3 )
    num = 1  ? No => devolver 3 * factorial( 2 )
        Tercera llamada: factorial( 3 )
        num = 1  ? No => devolver 2 * factorial( 1 )
            Cuarta llamada: factorial( 1 )
            num = 1  ? Si => devolver 1
        Comienza la "sustitucion regresiva", rellenando los datos
        que antes no se conocian y que han quedado pendientes:
        Resolucion de factorial( 2 ): 2 * factorial(1) = 2 * 1 = 2
    Resolucion de factorial( 3 ): 3 * factorial(2) = 3 * 2 = 6
Resolucion de factorial( 4 ): 4 * factorial(3) = 4 * 6 = 24

Como se puede observar, muchos datos intermedios no tienen valor inicialmente y quedan pendientes de ser "rellenados" cuando ya se ha llegado al caso base y se "regresa" desde él. Eso hace que las funciones recursivas sean "costosas" en uso de memoria, pero en ocasiones hacen que la solución del problema sea más sencilla y legible, y en ciertos casos puntuales una función recursiva será la única solución.

Ejercicio propuesto 6.5.1: Crear otra función que halle la potencia (a elevado a b) de dos números enteros positivos, de forma recursiva, usando varias multiplicaciones. Pista: el caso base, la potencia más sencilla, será si elevas un número a 1, caso en el que obtienes el mismo número. Para el caso general, tendrás que pensar cómo pasar de la potencia "n" a la "n-1", por ejemplo de 36 a 35.
Ejercicio propuesto 6.5.2: Crea una función recursiva que halle el producto de dos números enteros positivos, usando sumas.
Ejercicio propuesto 6.5.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 6.5.4: Crea una función recursiva que devuelva invertida la cadena de texto que se pase como parámetros (piensa cuántos elementos deberá tener la cadena más sencilla y de invertir, y cómo invertir una cadena de longitud "n" si ya sabes cómo quedan invertidas sus "n-1" primeras (o últimas) letras.
Ejercicio propuesto 6.5.5: Crea un programa que emplee recursividad para calcular la suma de los elementos de un vector (piensa cuántos elementos deberá tener el caso base, el más sencillo, y como pasar de los "n" primeros elementos a los "n+1" primeros (o últimos).
Ejercicio propuesto 6.5.6: 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).