Diferencia entre revisiones de «Programación en Pascal/Funciones y procedimientos»
Contenido eliminado Contenido añadido
Línea 296:
=Recursividad=
Recursividad.
Vamos al segundo apartado de hoy: qué es eso de la "recursividad". Pues la idea en sí es muy sencilla: un procedimiento o función es recursivo si se llama a sí mismo.
¿Y 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.
Vamos a verlo con un ejemplo clásico: el factorial de un número.
Partimos de la definición de factorial de un número n:
n! = n · (n-1) · (n-2) · ... · 3 · 2 · 1
Por otra parte, el factorial del siguiente número más pequeño (n-1) es
(n-1)! = (n-1) · (n-2) · ... · 3 · 2 · 1
Se parecen mucho. Luego podemos escribir cada factorial en función del factorial del siguiente número:
n! = n · (n-1)!
¡Acabamos de dar la definición recursiva del factorial! Así 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.
Pues ahora sólo queda ver cómo se haría eso programando:
{--------------------------}
{ Ejemplo en Pascal: }
{ }
{ Factorial, ejemplo de }
{ recursividad }
{ FACT.PAS }
{ }
{ Este fuente procede de }
{ CUPAS, curso de Pascal }
{ por Nacho Cabanes }
{ }
{ Comprobado con: }
{ - Turbo Pascal 7.0 }
{ - Turbo Pascal 5.0 }
{ - Surpas 1.00 }
{--------------------------}
program PruebaDeFactorial;
var numero: integer;
function factorial( num : integer) : integer;
begin
if num = 1 then
factorial := 1 (* Aseguramos que tenga salida siempre *)
else
factorial := num * factorial( num-1 ); (* Caso general *)
end;
begin
writeln( 'Introduce un número entero (no muy grande) guiño' );
readln(numero);
writeln( 'Su factorial es ', factorial(numero) );
end.
Un par de comentarios sobre este programilla:
* Atención a la primera parte de la función recursiva: es muy importante comprobar que hay salida de la función, para que no se quede dando vueltas todo el tiempo y nos cuelgue el ordenador. Normalmente, la condición de salida será que ya hallamos llegado al caso fácil (en este ejemplo: el factorial de 1 es 1).
* No pongais números demasiado grandes. Recordad que los enteros van desde -32768 hasta 32767, luego si el resultado es mayor que este número, tendremos un desbordamiento y el resultado será erróneo. ¿Qué es "demasiado grande"? Pues el factorial de 8 es cerca de 40.000, luego sólo podremos usar números del 1 al 7.
Si este límite del tamaño de los enteros os parece preocupante, no le deis muchas vueltas, porque en la próxima lección veremos que hay otros tipos de datos que almacenan números más grandes o que nos permiten realizar ciertas cosas con más comodidad.
| |||