Recursividad
Páginas: 5 (1248 palabras)
Publicado: 1 de febrero de 2013
RECURSIVIDAD
La recursividad forma parte del repertorio para resolver problemas en Computación y es de los métodos más poderosos y usados.
Los algoritmos recursivos ofrecen soluciones estructuradas, modulares y elegantemente simples.
La recursividad es un concepto fundamental en matemáticas y en computación. Una definición recursiva dice cómo obtener conceptos nuevos empleando el mismoconcepto que intenta describir.
En toda situación en la cual la respuesta pueda ser expresada como una secuencia de movimientos, pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas, la fórmula recursiva es un buen candidado para resolver el problema.
Los razonamientos recursivos se encuentran en la base misma de las matemáticas porque son necesarios para describirconceptos centrales como el de número:
Ejemplo:
1. Factorial
Definición:
factorial (n) = n! si n > 0
factorial (n) = n*n-1*n-2* ... * 1 si n > 0
el valor de 0! se define como
factorial (0) = 1
Su definición recursiva es:
factorial (n) = 1 si n = 0
factorial (n) = n* factorial (n-1) si n > 0
así para calcular el factorial de 4:
factorial (4) = 4 * factorial (3)= 4 * 6 = 24
factorial (3) = 3 * factorial (2) = 3 *2 = 6
factorial (2) = 2 * factorial (1) = 2 * 1 = 2
factorial (1) = 1 * factorial (0) = 1 * 1 = 1
estática int factorial (int n)
comienza
si n = 0 entonces
regresa 1
otro
regresa factorial (n-1) * n
termina
Versión iterativa:
estática int factorial (int n)
comienza
fact ( 1
para i ( 1 hasta n
fact ( i * factregresa fact
termina
Las definiciones recursivas de funciones en matemáticas que tienen como argumentos números enteros, se llaman relaciones de recurrencia.
Forma de una ecuación de recurrencia:
coar +c1ar-1 + c2ar-2 + ....+ ckar-k = f(r) función matemática discreta
donde ci son constantes, es llamada una ecuación de recurrencia de coeficientes constantes de orden k, condicionadaa que c0 y ck = 0.
Una definición recursiva dice cómo obtener conceptos nuevos empleando el mismo concepto que intenta definir.
El poder de la recursividad es que los procedimientos o conceptos complejos pueden expresarse de una forma simple.
Un razonamiento recursivo tiene dos partes: la base y la regla recursiva de construcción. La base no es recursiva y es el punto tanto de partidacomo de terminación de la definición.
Ejemplo:
Base: La secuenciación, iteración condicional y selección son estructuras válidas de control que pueden ser consideradas como enunciados.
Regla recursiva: Las estructuras de control que se pueden formar combinando de manera válida la secuenciación iteración condicional y selección también son válidos.
Un conjunto de objetos está definidorecursivamente siempre que:
(B) algunos elementos del conjunto se especifican explícitamente
(R) el resto de los elementos del conjunto se definen en términos de los elementos ya definidos
donde
(B) se llama base
(R) se llama cláusula recursiva
Observaciones:
1. El procedimiento se llama a si mismo
2. El problema se resuelve, resolviendo el mismo problema pero de tamaño menor
3.La manera en la cual el tamaño del problema disminuye asegura que el caso base eventualmente se alcanzará
La recursividad es un método poderoso usado en inteligencia artificial, su poder es que algunos conceptos complejos pueden expresarse en una forma simple. Una definición recursiva difiere de una definición circular en que tiene una forma de escapar de su expansión infinita. Este escape seencuentra en la definición o porción no recursiva o terminal de la definición.
Las fórmulas recursivas pueden aplicarse a situaciones tales como prueba de teoremas, solución de problemas combinatorios, algunos acertijos, etc.
Ejemplos:
1. Números de Fibonacci
Los números de Fibonacci se definen como:
FN = FN-1 + FN-2 para N > 2
F0 = F1 = 1
que definen la secuencia:...
La recursividad forma parte del repertorio para resolver problemas en Computación y es de los métodos más poderosos y usados.
Los algoritmos recursivos ofrecen soluciones estructuradas, modulares y elegantemente simples.
La recursividad es un concepto fundamental en matemáticas y en computación. Una definición recursiva dice cómo obtener conceptos nuevos empleando el mismoconcepto que intenta describir.
En toda situación en la cual la respuesta pueda ser expresada como una secuencia de movimientos, pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas, la fórmula recursiva es un buen candidado para resolver el problema.
Los razonamientos recursivos se encuentran en la base misma de las matemáticas porque son necesarios para describirconceptos centrales como el de número:
Ejemplo:
1. Factorial
Definición:
factorial (n) = n! si n > 0
factorial (n) = n*n-1*n-2* ... * 1 si n > 0
el valor de 0! se define como
factorial (0) = 1
Su definición recursiva es:
factorial (n) = 1 si n = 0
factorial (n) = n* factorial (n-1) si n > 0
así para calcular el factorial de 4:
factorial (4) = 4 * factorial (3)= 4 * 6 = 24
factorial (3) = 3 * factorial (2) = 3 *2 = 6
factorial (2) = 2 * factorial (1) = 2 * 1 = 2
factorial (1) = 1 * factorial (0) = 1 * 1 = 1
estática int factorial (int n)
comienza
si n = 0 entonces
regresa 1
otro
regresa factorial (n-1) * n
termina
Versión iterativa:
estática int factorial (int n)
comienza
fact ( 1
para i ( 1 hasta n
fact ( i * factregresa fact
termina
Las definiciones recursivas de funciones en matemáticas que tienen como argumentos números enteros, se llaman relaciones de recurrencia.
Forma de una ecuación de recurrencia:
coar +c1ar-1 + c2ar-2 + ....+ ckar-k = f(r) función matemática discreta
donde ci son constantes, es llamada una ecuación de recurrencia de coeficientes constantes de orden k, condicionadaa que c0 y ck = 0.
Una definición recursiva dice cómo obtener conceptos nuevos empleando el mismo concepto que intenta definir.
El poder de la recursividad es que los procedimientos o conceptos complejos pueden expresarse de una forma simple.
Un razonamiento recursivo tiene dos partes: la base y la regla recursiva de construcción. La base no es recursiva y es el punto tanto de partidacomo de terminación de la definición.
Ejemplo:
Base: La secuenciación, iteración condicional y selección son estructuras válidas de control que pueden ser consideradas como enunciados.
Regla recursiva: Las estructuras de control que se pueden formar combinando de manera válida la secuenciación iteración condicional y selección también son válidos.
Un conjunto de objetos está definidorecursivamente siempre que:
(B) algunos elementos del conjunto se especifican explícitamente
(R) el resto de los elementos del conjunto se definen en términos de los elementos ya definidos
donde
(B) se llama base
(R) se llama cláusula recursiva
Observaciones:
1. El procedimiento se llama a si mismo
2. El problema se resuelve, resolviendo el mismo problema pero de tamaño menor
3.La manera en la cual el tamaño del problema disminuye asegura que el caso base eventualmente se alcanzará
La recursividad es un método poderoso usado en inteligencia artificial, su poder es que algunos conceptos complejos pueden expresarse en una forma simple. Una definición recursiva difiere de una definición circular en que tiene una forma de escapar de su expansión infinita. Este escape seencuentra en la definición o porción no recursiva o terminal de la definición.
Las fórmulas recursivas pueden aplicarse a situaciones tales como prueba de teoremas, solución de problemas combinatorios, algunos acertijos, etc.
Ejemplos:
1. Números de Fibonacci
Los números de Fibonacci se definen como:
FN = FN-1 + FN-2 para N > 2
F0 = F1 = 1
que definen la secuencia:...
Leer documento completo
Regístrate para leer el documento completo.