Extructuras

Recursividad:
La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 *..., incrementando el número de 1 en 1 hasta llegaral número para el que se está calculando el factorial.
La recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa. Normalmente, un cálculo determinado se prestará a una técnica u otra, sólo necesita elegir el enfoque más natural o con el que se sienta más cómodo.
Como definicióngeneral, podemos decir que una función recursiva es aquella que se llama a si misma para resolverse. Dicho de otra manera, una función recursiva se resuelve con una llamada a si misma, cambiando el valor de un parámetro en la llamada a la función. A través de las sucesivas llamadas recursivas a la función se van obteniendo valores que, computados, sirven para obtener el valor de la función llamadaoriginalmente.
El proceso de llamadas recursivas siempre tiene que acabar en una llamada a la función que se resuelve de manera directa, sin necesidad de invocar de nuevo la función. Esto será siempre necesario, para que llegue un momento que se corten las llamadas reiterativas a la función y no se entre en un bucle infinito de invocaciones.
Aspecto de un subalgoritmo recursivo.

ALGORITMORecursivo(...)
INICIO
...
Recursivo(...);
...
FIN

Ejemplo: Factorial de un natural.
1 si n == 0
Factorial(n)=
n*Factorial(n-1) si n > 0

ALGORITMO N Factorial (E n: N)
VAR
N fact
INICIO
SI n == 0 ENTONCES fact = 1
SINO fact = n*Factorial(n-1)
FINSI
DEVOLVER fact
FIN
Tipos de recursión:

Estructuralmente existen dos formas de recursión:

1. la directa: es la quehemos visto hasta ahora en la que la función se llama a si misma.

2. Indirecta: es la recursión que se produce cuando la funcion se llama no a si misma sino
a otra función (y esta quizás a otra) que termina llamando a la función inicial. Se produce
así una cadena:
f(a) ! g(b) ! h(c) ! . . . f(a0)
Así la recursión directa es una forma mas simple de recursión en la que no existen g(), h(), etc.Existen distintos modos de hacer la recursión:
de cabeza la recursión de cabeza se produce cuando la llamada recursiva se hace justo al principio
del procedimiento recursivo, antes que ninguna otra operación.

Programación Recursiva:
Es mucho mas difícil desarrollar una solución recursiva en C para resolver un problema específico cuando no se tiene un algoritmo. No es solo el programa sinolas definiciones originales y los algoritmos los que deben desarrollarse. En general, cuando encaramos la tarea de escribir un programa para resolver un problema no hay razón para buscar una solución recursiva. La mayoría de los problemas pueden resolverse de una manera directa usando métodos no recursivos. Sin embargo, otros pueden resolverse de una manera más lógica y elegante mediante larecursión.

EJEMPLO 1:

FUNCIÓN COMBINACIONES

Calcular cuantas combinaciones de tamaño Miembros
Pueden hacerse del tamaño total Grupo
Tamaño: Número de procesos dado en la llamada original
Casos-base:1) Miembros==1 Combinaciones=Grupo
Miembros==Grupo Combinaciones=1
Caso General: Grupo>Miembros>1
Combinaciones = Combinaciones (Grupo-1 , Miembros -1) +
Combinaciones (Grupo-1,Miembros)
ALGORITMO N Comb(E N Grupo, Miembros)
VAR
N cmb
INICIO
SI Miembros == 1 ENTONCES
cmb = Grupo (*Caso Base 1*)
SINOSI Miembros == Grupo ENTONCES
cmb = 1 (*Caso Base 2*)
SINO (*Caso General*)
cmb = Comb(Grupo-1,Miembros-1) +
Comb(Grupo-1,Miembros)
FINSI
DEVOLVER cmb
FIN
Llamada : Escribir(“Número de combinaciones=“, Comb(20,5))

Ejemplo 2:
FUNCIÓN FIBONACCI
Calcular el valor...