6.5. Recursividad

  Curso: Programación en Pascal (v5), por Nacho Cabanes

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:

• Por una parte, hay que asegurarse de encontrar un caso "trivial", en el que la solución sea evidente. En este ejemplo, se trata del factorial del 1, cuyo valor es 1 (por convenio, se suele considerar que el factorial de 0 también es 1, pero no es un detalle que nos deba preocupar ahora). El resto de valores deberán acercarse a ese valor, para reducir un problema complejo a uno cada vez más simple.
• Por otra parte, hay que buscar una forma de "reducir el problema": el "caso general" debe indicar cómo se pasa de la solución para "n" a la solución para un caso más simple, que típicamente será "n-1". Si no nos vamos acercando al "caso base", nuestra función podría "quedarse colgada", y no salir nunca, o acabar "saturando la memoria" del ordenador, provocando un fallo conocido como "desbordamiento de pila".
• En el caso concreto del factorial, no deberíamos poner números demasiado grandes. Los enteros en Pascal estándar van desde -32768 hasta 32767, luego si el resultado es mayor que este número, tendremos un desbordamiento y el resultado será erróneo. El factorial de 8 es cerca de 40.000, luego sólo podremos usar números del 1 al 7. Si empleamos enteros largos, ganaremos un poco de margen de maniobra, pero aun así enseguida desbordaremos su valor.

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 ciertos casos puntuales serán 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 3⁶ a 3⁵.

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).

Actualizado el: 20-07-2014 23:59