Programar en c++

Introducción a la Recursión

Laboratorio de Programación. _____________________________________________________________________________

7

INTRODUCCIÓN A LA RECURSIVIDAD.

Contenido_____________________________________________________________________________ 7.1.- Concepto de recursión. 7.2.- Ejemplos de programas recursivos. 7.3.- Búsqueda y ordenación usando recursión. 7.3.1.-Búsqueda. 7.3.2.- Ordenación. Ejercicios _____________________________________________________________________________

7.1.- CONCEPTO DE RECURSION Se dice que un proceso es recursivo si se puede definir entérminos de si mismo, y a dicha definición se le denomina definición recursiva. La recursividad es una nueva forma de ver las acciones repetitivas permitiendo que un subprograma se llame a sí mismopara resolver una versión más pequeña del problema original. La función factorial es una función que se puede definir recursivamente y cuyo dominio es el de los enteros positivos. La función factorial,que se representa con el símbolo de exclamación, se define como: n! = n × (n - 1) × (n - 2) × ... × 1 lo cual significa que n! es igual al producto de todos los enteros no negativos entre n y 1,inclusivos. Consideremos los factoriales de los enteros no negativos del 1 al 5: 1! = 1 2! = 2 × 1 3! = 3 × 2 × 1 4! = 4 × 3 × 2 × 1 5! = 5 × 4 × 3 × 2 × 1____________________________________________________________________________________ Dpto. Lenguajes y Ciencias de la Computación I.T.I. Informática Gestión/Sistemas. UMA. Curso 2004/05. 1

Introducción a la Recursión

Laboratorio deProgramación. _____________________________________________________________________________ Si nos fijamos atentamente en las operaciones anteriores, podremos extraer una propiedad bastante interesante dela función factorial. Empecemos con el 5! , que es igual a: 5! = 5 × (4 × 3 × 2 × 1) pero lo que hay dentro del paréntesis es 4!, es decir (5 - 1)!, lo cual significa que : 5! = 5 × 4! Similarmente,...