recursividad

 Recursividad: Conceptos básicos


Primero debemos decir que la recursividad no es una estructura de datos, sino que es una técnica de programación que nos permite que un bloque de instrucciones se ejecute n veces. Remplaza en ocasiones a estructuras repetitivas.
Este concepto será de gran utilidad para el capítulo de la estructura de datos tipo árbol.
La recursividad es un concepto difícilde entender en principio, pero luego de analizar diferentes problemas aparecen puntos comunes.
En C# los métodos pueden llamarse a sí mismos. Si dentro de un método existe la llamada a sí mismo decimos que el método es recursivo.
Cuando un método se llama a sí mismo, se asigna espacio en la pila para las nuevas variables locales y parámetros.
Al volver de una llamada recursiva, se recuperan dela pila las variables locales y los parámetros antiguos y la ejecución se reanuda en el punto de la llamada al método.
Problema 1:
Implementación de un método recursivo.
Programa:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Recursividad1
{
public class Recursividad
{

void Repetir()
{Repetir();
}

static void Main(string[] args)
{
Recursividad re = new Recursividad();
re.Repetir();
}

}
}
La función Repetir es recursiva porque dentro de la función se llama a sí misma.
Cuando ejecuta este programa se bloqueará y generará un error.
Analicemos como funciona:
Primero se ejecuta la función Main, luego de crear unobjeto llamamos a la función Repetir.
Hay que tener en cuenta que cada vez que se llama a una función se reservan 4 bytes de la memoria que se liberarán cuando finalice su ejecución.
La primera línea de la función llama a la función Repetir, es decir que se reservan 4 bytes nuevamente. Se ejecuta nuevamente una instancia de la función Repetir y así sucesivamente hasta que la pila estática se colmey se cuelgue el programa.
Problema 2:
Implementación de un método recursivo que reciba un parámetro de tipo entero y luego llame en forma recursiva con el valor del parámetro menos 1.
Programa:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Recursividad2
{
public class Recursividad
{

void Imprimir(int x)
{Console.Write(x + " ");
Imprimir(x - 1);
}

static void Main(string[] args)
{
Recursividad re = new Recursividad();
re.Imprimir(5);
}
}
}
Desde la Main se llama a la función Imprimir y se le envía el valor 5. El parámetro x recibe el valor 5. Se ejecuta el algoritmo de la función, imprime el contenido delparámetro (5) y seguidamente se llama a una función, en este caso a sí misma (por eso decimos que es una función recursiva), enviándole el valor 4.
El parámetro x recibe el valor 4 y se imprime en pantalla el cuatro, llamando nuevamente a la función imprimir enviándole el valor 3.
Si continuamos este algoritmo podremos observar que en pantalla se imprime:
5 4 3 2 1 0 –1 –2 –3 . . . . . . . ..
hasta que se bloquee el programa.
Tener en cuenta que cada llamada a una función consume 4 bytes por la llamada y en este caso 4 bytes por el parámetro x. Como nunca finaliza la ejecución completa de las funciones se desborda la pila estática por las sucesivas llamadas.
Problema 3:
Implementar un método recursivo que imprima en forma descendente de 5 a 1 de uno en uno.
Programa:
publicclass Recursividad {

void imprimir(int x) {
if (x>0) {
System.out.println(x);
imprimir(x-1);
}
}

public static void main(String[] ar) {
Recursividad re=new Recursividad();
re.imprimir(5);
}
}
Ahora si podemos ejecutar este programa y observar los resultados en pantalla. Se imprimen los números 5 4 3 2 1...