Recursividad

Recursividad

Definición

Un procedimiento o función se dice recursivo si durante su ejecución se invoca directa o indirectamente a sí mismo. Esta invocación depende al menos de una condición que actúa como condición de corte que provoca la finalización de la recursión.
Un algoritmo recursivo consta de:
1- Al menos un caso trivial o base, es decir, que no vuelva a invocarse y que seejecuta cuando se cumple cierta condición, y
2- el caso general que es el que vuelve a invocar al algoritmo con un caso más pequeño del mismo.
Los lenguajes como Pascal, que soportan recursividad, dan al programador una herramienta poderosa para resolver ciertos tipos de problemas reduciendo la complejidad u ocultando los detalles del problema.
La recursión es un medio particularmentepoderoso en las definiciones matemáticas. Para apreciar mejor cómo es una llamada recursiva, estudiemos la descripción matemática de factorial de un número entero no negativo:

1, si n = 0
n! =
n * ( n - 1 ) * ( n - 2 ) * .. * 1 = n * ( n - 1 )! si n > 0

Estadefinición es recursiva ya que expresamos la función factorial en términos de sí misma.
Ejemplo: 4! = 4 * 3!
Por supuesto, no podemos hacer la multiplicación aún, puesto que no sabemos el valor de 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1
Podemos ahora completar los cálculos
1! = 1 * 1 = 1
2! = 2 * 1 = 2
3! = 3 * 2 = 6
4! = 4 * 6 = 24

Diseño de AlgoritmosRecursivos

Para que una función o procedimiento recursivo funcione se debe cumplir que:
• Existe una salida no recursiva del procedimiento o función y funciona correctamente en ese caso.
• Cada llamada al procedimiento o función se refiere a un caso más pequeño del mismo.
• Funciona correctamente todo el procedimiento o función.

Para poder construir cualquier rutina recursivateniendo en cuenta lo anterior, podemos usar el siguiente método:
• Primero, obtener una definición exacta del problema.
• A continuación, determinar el tamaño del problema completo a resolver. Así se determinarán los valores de los parámetros en la llamada inicial al procedimiento o función.
• Tercero, resolver el caso base en el que problema puede expresarse no recursivamente. Estoasegurará que se cumple el punto 1 del test anterior.
• Por último, resolver correctamente el caso general, en términos de un caso más pequeño del mismo problema (una llamada recursiva). Esto asegurará cumplir con los puntos 2 y 3 del test.

Cuando el problema tiene una definición formal, posiblemente matemática, como el ejemplo del cálculo del factorial, el algoritmo deriva directamente y esfácilmente implementable en otros casos debemos encontrar la solución más conveniente.

Ejemplo

Cálculo del factorial para enteros no negativos

1, si n = 0

n! =
n * ( n - 1 ) ! si n > 0

Diagrama de Llaves:

(*Pre: n >= 0*)

n = 0Factorial ( 1 (*Caso base*)

Factorial(n) (

n = 0 Factorial ( n * Factorial (n-1) (*Caso Gral*)

(*Pos: Factorial = n!*)

Código Pascal:

function factorial(n: integer):integer;
begin
if n=0 then factorial = 1 (* caso base *)
elsefactorial = n * factorial(n-1) (* caso general *)
end;

Cómo funcionan los Algoritmos Recursivos

Para entender cómo funciona la recursividad es necesario que tengamos presente las reglas y los tipos de pasaje de parámetros provistos por Pascal.
Si un procedimiento o función p invoca a otro q, durante la ejecución de q se reservarán locaciones de memoria...