Recursividad

 Recursividad.

Introducción.

La recursividad consiste en realizar una definición de un

concepto en términos del propio concepto que se está definiendo.

Ejemplos:

·

0 es un Número natural y el sucesor de un número natural

es también un número natural.

Los números naturales se pueden definir de la siguiente forma:

·

o n multiplicado por el factorial del número n-1, en caso

contrario.

El factorial de un número natural n, es 1 si dicho número es 0,

·

producto de x por la potencia (n-1)-ésima de x, cuando n es

mayor que 0.

En todos estos ejemplos se utiliza el concepto definido en la

propia definición.

La n-ésima potencia de un número x, es 1 si n es igual a 0, o el

Solución de problemas recursivos:

·

pequeños, del mismo tipo que el inicial.

División sucesiva del problema original en uno o varios más

·

Se van resolviendo estos problemas más sencillos.

·

problemas más complejos.

O lo que es lo mismo:

1.Un problema P se puede resolver conociendo la solución de

otro problema Q que es del mismo tipo que P, pero más

pequeño.

2.Igualmente, supongamos que pudiéramos resolver Q

mediante la búsqueda de la solución de otro nuevo

problema, R, que sigue siendo del mismo tipo que Q y P,

pero de un tamaño menor que ambos.

3.Si el problema R fuera tan simple que su solución es obvia o

directa, entonces, dado que sabemos la solución de R,

procederíamos a resolver Q y, una vez resuelto, finalmente

se obtendría la solución definitiva al primer problema, P.

Con las soluciones de éstos se construyen las soluciones de los

Ejemplos simples de

recursividad.

A) Cálculo del factorial de un número, por ejemplo, 5.

5! = 5 * 4!

4! = 4 * 3!

3!= 3 * 2!

2! = 2 * 1!

DESCOMPOSICIÓN

DEL PROBLEMA

1! = 1 * 0!

SOLUCIÓN CONOCIDA O DIRECTA

0! = 1

1! = 1 * 0! = 1

2! = 2 * 1! = 2

3! = 3 * 2! = 6 RESOLUCIÓN DE

PROBLEMAS MÁS

COMPLEJOS A PARTIR

4! = 4 * 3! = 24 DE OTROS MÁS

SIMPLES

5! = 5 * 4! = 120

B) Búsqueda de una palabra en un diccionario.

Características de los problemas que pueden ser

resueltos de manera recursiva:

4.Los problemas pueden ser redefinidos en términos de uno o

más subproblemas, idénticos en naturaleza al problema

original, pero de alguna forma menores en tamaño.

5.Uno o más subproblemas tienen solución directa o conocida,

no recursiva.

6.Aplicando la redefinición del problema en términos de

problemas más pequeños, dicho problema se reduce

sucesivamente a los subproblemas cuyas soluciones se

conocen directamente.

7.La solución a los problemas más simples se utiliza para

construir la solución al problema inicial.

Algoritmos recursivos:

diseño de la solución de un problema de manera recursiva

El algoritmo se llamará a sí mismo varias veces

¡Ojo al diseñar algoritmos recursivos!

pueden ser menos eficientes que que su solución iterativa

Algoritmo recursivo

nivel que permita recursividad (en nuestro caso, en Java).

Implementación en un lenguaje de alto