Recursividad

Recursividad:

Las funciones en C pueden ser recursivas, es decir una función que se llama a sí misma se denomina recursiva, pueden llamarse a sí mismas directa o indirectamente.
Entonces un algoritmo recursivo es aquel que se llama así mismo con el fin de resolver determinados problemas. 
Un proceso recursivo tiene que tener una condición de finalización, ya que de lo contrario podríacontinuar infinitamente, es decir para que sea correcto un algoritmo recursivo es que no genere una secuencia infinita de llamadas así mismo. Ya que cualquier algoritmo que genere tal secuencia no termina nunca.
La recursividad es una herramienta muy importante en la programación que en muchos casos permite expresar algoritmos de forma simple y legible.

.
Sintaxis:<tipo_de_regreso><nom_fnc> (<param>)
{
[Declaración de variables]
[Condición de salida]
[Instrucciones]
[Llamada a <nom_fnc> (<param>)]
return <resultado>
}
.
El ejemplo más común, que se utiliza para explicar la recursividad, es el caso del cálculo de factorial

Ejemplos:
El cálculo de la factorial utilizando pseudocódigo, y codificación Basic y C 

Pseudocódigo: Función Factorial 
Si n = 0 
Entonces n!=1 
Si n > 0  
Entonces n! = n*(n-1)! 
 
Codificacion Basic: 

Public Function Factorial (Byval n As Integer) As Long 
If n = 0 Then  
Return 1 
Else 
Return (n*Factorial (n - 1)) 
End If 
End Function 
 
Codificacion C: 

Long Factorial (int n) 
{ 
if (n == 0) 
return  1; 
else 
return  n*(factorial(n – 1)); 
} En java:
Programar un algoritmo recursivo que permita sumar los elementos de un vector.

intsuma_vec(intv[],intn)
   {
if(n==0)
   returnv[n];
else
   returnsuma_vec(v, n-1) + v[n];
   }
Eficacia de la recursividad:
Se dice que es menos eficaz que la iterativa porque ocupa más memoria y mayor tiempo de ejecución pero hace el programa más sencillo y comprensible. Un programarecursivo se puede transformar en una solución iterativa mediante el uso de pilas.

TIPOS DE RECURSIVIDAD
1. Recursividad Simple:
en cuya definición sólo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iterativos.
2. Recursividad Múltiple:
Se da cuando hay más de una llamada a sí misma dentro del cuerpo de la función, resultando más difícil de hacer de formaiterativa.
int Fib( int n ) /* ej: Fibonacci */
{ if(n<=1) return(1);
return(Fib(n-1) + Fib(n-2)); }
3. Recursividad Anidada:
Algunos de los argumentos de la llamada recursiva hay una nueva llamada a sí misma.

int Ack( int n, int m ) /* ej: Ackerman */
{ if(n==0 ) return(m+1);
else if(m==0) return(Ack(n-1,1));
return(Ack(n-1, Ack(n,m-1)));
}

4. La recursividaddirecta
Este tipo de recursividad se muestra en aquellas funciones que se invocan asi mismas. 
 
Ejemplo: 

FUNCIÓN Factorial(n) 
VAR resultado: Entero 
  SI (n<2) ENTONCES 
resultado = 1; 
SINO 
 resultado = n * Factorial(n-1); 
FSI 
RETORNA resultado; 
FFUNCIÓN 

5. Recursividad indirecta:

En este otro caso la función se invoca así misma haciéndoloindirectamente desde otra. 
Ejemplo: 

Subrutina_A → Subrutina_B → Subrutina_A 
Subrutina_A → Subrutina_B → Subrutina_C → Subrutina_D → Subrutina_A 

Ejemplo:
Int par(int n);
int impar(int n);

intpar(int n)
{
if(n == 0) return 1;
return impar(n-1);
}
Int impar(int n)
{
if(n == 0) return 0;
returnpar(n-1);
}

Recursividad Vs Iteración:
En las secciones anteriores se hanestudiado varias funciones que se pueden implementar fácilmente o de modo recursivo o bien de modo iterativo. En esta parte compararemos los dos enfoques y examinaremos las razones por las que el programador puede elegir u enfoque u otro según la situación específica.

Tanto la iteración como la recursión se basan en una estructura de control:
* La iteración utiliza una estructura repetitiva....