Nuevos Programadores

En este ejemplo tenemos una aplicación simple que pide un número y lo convierte a binario utilizando un algoritmo recursivo con una variable externa.

Lo primero que tenemos que saber es cómo convertir un número de base 10 a binario, (base 2). Para ello, se divide el número deseado entre 2 y cada resultado de la división tantas veces como sea necesario hasta obtener el número indivisible, el 1. Luego se toman el último resultado, 1 y todos los restos de las divisiones, viendo la imagen va a quedar mucho más claro el concepto.

A continuación veremos el código en Java necesario para pedir el número en base 10 y devolverlo en binario, por supuesto que se pueden agregar validaciones, de hecho hay que agregar validaciones para asegurarnos que el usuario ingrese un número, pero ese no es el objetivo de este post.

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class binario
{
	public static void main(String[] args)
	{
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader rdr = new BufferedReader(isr);
		System.out.print("Ingrese un número entero: ");
		String buffer = "0";
		try
		{
			buffer = rdr.readLine();
		}
		catch(java.io.IOException e) // Es obligatorio manejar la IOException, si se omite no compila
		{
			System.out.println(e);
		}
 
		int dec = Integer.parseInt(buffer);
		System.out.print("El valor binario correspondiente es: ");
 
		if(dec == 0)
			System.out.println(dec); // Cero en cualquier base es cero
		else
			System.out.println(obtenerBinario(dec)); // llamamos a la func. recursiva
	}
 
 
	static String aux = ""; // variable auxiliar utilizada para almacenar el resto de cada división
 
	static String obtenerBinario(int decimal)
	{
		if(decimal == 1) // Límite de la recursividad
			return Integer.toString(decimal) + aux; // Devolvemos 1 y los restos anteriores
		else
		{
			aux = aux + Integer.toString(decimal % 2); //guardamos el resto en la variable auxiliar
			return obtenerBinario(decimal / 2); // hacemos el llamado recursivo con el resultado de la división
		}
	}
}

Además del algoritmo para convertir los números, vale la pena ver la forma en que se lee la entrada estándar, utilizando un BufferedReader, pero eso lo veremos con mayor profundidad en otro post.

}

Siguiendo con el tema Recursividad, ahora vamos a ver un ejemplo en C++ que es otro de los clásicos a la hora de aprender algoritmos recursivos, el cálculo del factorial de un número.

El factorial de un número n, se define como el producto de todos los números naturales comprendidos entre 1 y n, o sea que el factorial de 3 es 1 x 2 x 3 = 6. Por definición además, el factorial de 0 es 1.
Veamos lo anterior con ejemplos y a continuación la función iterativa para realizar el cálculo del factorial en C++.

• 3! = 3 x 2 x 1
• n! = n x (n-1) x (n-2) … x 1

int factorial(int n) { 
	int i; 
	int fact = 1; 
	for(i = 1; i <= n; i++) { 
		fact = fact * i; 
	} 
	return fact; 
}

Ahora si analizamos un poco más podemos ver que n! = n x (n-1)! (para n > 0), de donde surge la recursividad, ahora veamos un ejemplo y luego la función recursiva.

• 4! = 4 x 3 x 2 x 1
• 4! = 4 x 3!
• 3! = 3 x 2 x 1
• 3! = 3 x 2!
• 2! = 2 x 1

int factorial(int n) { 
	if(n == 0) { 
		return 1; 
	} 
	else 
	{ 
		return n * factorial(n-1); 
	} 
}

}

Los métodos de extensión, extension methods en inglés, son una de las novedades de la última versión de .Net Framework. Como su nombre lo indica, estos métodos permiten extender la funcionalidad de una clase sin la necesidad de tener el código fuente de la misma.

En VB.NET se utiliza un módulo para escribir los métodos de extensión, y justamente esa es la causa de muchas críticas negativas respecto a la utilización de éstos métodos.

Dentro del módulo necesitaremos definir los métodos y en su firma incluir el atributo que es el que definirá a nuestro método como método de extensión.

Luego hay que tener al menos un parámetro en la firma, que es el que indicará la clase que este método va a extender, por ejemplo hagamos un método para extender la clase String:

<Extension()> _ 
Public Function ReemplazoArroba(ByVal Cadena As String) As String 
	Return Cadena.Replace("@", "(a)") 
End Function

Entonces podremos llamar a nuestro método como un método de instancia:

Me.TextBox1.Text = Me.TextBox2.Text.ReemplazoArroba()

En la firma del método está el parámetro que define la clase que se extiende, pero a la hora de llamarlo, ese parámetro no se utiliza, ahora hagamos que nuestro método de extensión acepte en un parámetro el reemplazo que utilizará para el caracter @.

<Extension()> _
Public Function ReemplazoArroba(ByVal Cadena As String, Reemplazo as String) As String 
	Return Cadena.Replace("@", Reemplazo) 
End Function

Ahora si, a la hora de llamarlo tendremos que pasar el parámetro Reemplazo:

Me.TextBox1.Text = Me.TextBox2.Text.ReemplazoArroba("[arroba]") 

De la misma manera y en el mismo módulo podremos implementar métodos de extensión para varias clases, también se podrían implementar en un módulo ya existente de nuestro proyecto, pero por prolijidad yo prefiero hacerlo en uno aparte.

El siguiente método extiende la clase System.Windows.Forms.Control.ControlCollection y le agrega un método que puede resultar realmente útil, es un método que busca recursivamente todos los controles de tipo TextBox y borra su contenido.

<Extension()> _
Public Sub EmptyAllTextBoxes(ByVal Controls As Windows.Forms.Control.ControlCollection) 
	For Each c As Control In Controls 
		If c.Controls IsNot Nothing AndAlso c.Controls.Count > 0 Then 
			EmptyAllTextBoxes(c.Controls) ' Llamado recursivo 
		ElseIf c.GetType().Equals(GetType(TextBox)) Then 
			CType(c, TextBox).Text = String.Empty 
		End If 
	Next 
End Sub

Pueden descargar una solución de VS2008 con ejemplos de métodos de extensión (55.25 KB) para probar y modificar el código.

}

Utilizaremos JavaScript para estos ejemplos de recursividad.

Una función es recursiva cuando en su cuerpo hay un llamado a si misma, un ejemplo clásico es la operación matemática potencia, primero veamos la función no recursiva que defina la potencia:

function potencia(base, exponente) {
	 if(exponente == 0) { //caso límite de exponente cero
		return 1
	 } else {
		return base * potencia(base, exponente -1) //llamado recursivo
	 }
}

Para este caso tomaremos sólo las potencias de exponente positivo para no aumentar la complejidad del ejemplo.

Lo que haremos a continuación será analizar la función para convertirla en recursiva, primero los casos límite, sabemos que el resultado de toda potencia de exponente 0 es 1, entonces ese será nuestro primer chequeo.

Luego estudiemos la función a partir de un ejemplo, sea en este caso 2⁴:

• 2⁴ = 2 * 2 * 2 * 2 = 16
• 2 * 2 * 2 * 2 = 2 * (2³) = 2 * 8 = 16
• 2 * (2³) = 2 * (2 * (2²)) = 2 * (2 * 4) = 16

Visto lo anterior, podemos afirmar que x^y = x * (x^y-1) de donde claramente se desprende la recursividad, en palabras, potencia de x a la y = x por potencia de x a la y -1, vamos el código:

function potencia(base, exponente) { if(exponente == 0) { //caso límite de exponente cero return 1; } else { while(exponente >= 1) { return base * potencia(base, exponente -1); //llamado recursivo } } } 

Tal vez en este caso no es muy notorio, pero una de las principales ventajas de utilizar algoritmos recursivos es la disminución de la cantidad de líneas de código necesarias.

Estudiemos el caso de la sucesión de Fibonacci, otro ejemplo clásico de algoritmo recursivo.

Cada término de la sucesión de Fibonacci es la suma de los 2 términos predecesores, sabiendo que los primero términos, por definición son 0 y 1, entonces sabemos que los primeros 10 términos de la sucesión son:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Ahora podemos afirmar que además de los términos primarios f₀ = 0, f₁ = 1, un término enésimo se define como f_n = f_n-1 + f_n-2

Veamos una función recursiva que calcule el término n de la sucesión de Fibonacci:

function fibonacci(n) {
	if(n==0 || n== 1) { // casos límite 
		return n; 
	} else { 
		return fibonacci(n-1) + fibonacci(n-2); // suma del término anterior y su predecesor 
	} 	
}

Si llamamos a la función anterior en un bucle podremos obtener la sucesión hasta el término especificado en el bucle, por ejemplo:

var fib = "F: "; 
for(i = 0; i<= 9; i++) { 
	fib += fibonacci(i) + " | "; 
} 
document.write(fib);

Nos escribirá los primeros 10 términos de la sucesión de Fibonacci: F: 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 |

}