C# Language
Recursion

Observaciones

Describir recursivamente una estructura de objeto.

La recursividad es cuando un método se llama a sí mismo. Preferiblemente, lo hará hasta que se cumpla una condición específica y luego saldrá del método normalmente, volviendo al punto desde el cual se llamó el método. De lo contrario, podría producirse una excepción de desbordamiento de pila debido a demasiadas llamadas recursivas.

/// <summary>
/// Create an object structure the code can recursively describe
/// </summary>
public class Root
{
    public string Name { get; set; }
    public ChildOne Child { get; set; }
}
public class ChildOne
{
    public string ChildOneName { get; set; }
    public ChildTwo Child { get; set; }
}
public class ChildTwo
{
    public string ChildTwoName { get; set; }
}
/// <summary>
/// The console application with the recursive function DescribeTypeOfObject
/// </summary>
public class Program
{
    static void Main(string[] args)
    {
        // point A, we call the function with type 'Root'
        DescribeTypeOfObject(typeof(Root));
        Console.WriteLine("Press a key to exit");
        Console.ReadKey();
    }

    static void DescribeTypeOfObject(Type type)
    {
        // get all properties of this type
        Console.WriteLine($"Describing type {type.Name}");
        PropertyInfo[] propertyInfos = type.GetProperties();
        foreach (PropertyInfo pi in propertyInfos)
        {
            Console.WriteLine($"Has property {pi.Name} of type {pi.PropertyType.Name}");
            // is a custom class type? describe it too
            if (pi.PropertyType.IsClass && !pi.PropertyType.FullName.StartsWith("System."))
            {
                // point B, we call the function type this property
                DescribeTypeOfObject(pi.PropertyType);
            }
        }
        // done with all properties
        // we return to the point where we were called
        // point A for the first call
        // point B for all properties of type custom class
    }
}

Recursion en ingles llano

La recursión se puede definir como:

Un método que se llama a sí mismo hasta que se cumple una condición específica.

Un ejemplo excelente y simple de recursión es un método que obtendrá el factorial de un número dado:

public int Factorial(int number)
{
    return number == 0 ? 1 : n * Factorial(number - 1);
}

En este método, podemos ver que el método tomará un argumento, number .

Paso a paso:

Dado el ejemplo, ejecutando Factorial(4)

1. ¿Es el number (4) == 1 ?
2. ¿No? retorno 4 * Factorial(number-1) (3)
3. Debido a que se vuelve a llamar al método, ahora repite el primer paso utilizando Factorial(3) como el nuevo argumento.
4. Esto continúa hasta que se ejecuta Factorial(1) y el number (1) == 1 devuelve 1.
5. En general, el cálculo "acumula" 4 * 3 * 2 * 1 y finalmente devuelve 24.

La clave para comprender la recursión es que el método llama a una nueva instancia de sí mismo. Después de volver, la ejecución de la instancia de llamada continúa.

Usando la recursividad para obtener el árbol de directorios

Uno de los usos de la recursión es navegar a través de una estructura de datos jerárquica, como un árbol de directorios del sistema de archivos, sin saber cuántos niveles tiene el árbol o la cantidad de objetos en cada nivel. En este ejemplo, verá cómo usar la recursión en un árbol de directorios para encontrar todos los subdirectorios de un directorio específico e imprimir todo el árbol en la consola.

internal class Program
{
    internal const int RootLevel = 0;
    internal const char Tab = '\t';

    internal static void Main()
    {
        Console.WriteLine("Enter the path of the root directory:");
        var rootDirectorypath = Console.ReadLine();

        Console.WriteLine(
            $"Getting directory tree of '{rootDirectorypath}'");

        PrintDirectoryTree(rootDirectorypath);
        Console.WriteLine("Press 'Enter' to quit...");
        Console.ReadLine();
    }

    internal static void PrintDirectoryTree(string rootDirectoryPath)
    {
        try
        {
            if (!Directory.Exists(rootDirectoryPath))
            {
                throw new DirectoryNotFoundException(
                    $"Directory '{rootDirectoryPath}' not found.");
            }

            var rootDirectory = new DirectoryInfo(rootDirectoryPath);
            PrintDirectoryTree(rootDirectory, RootLevel);
        }
        catch (DirectoryNotFoundException e)
        {
            Console.WriteLine(e.Message);
        }
    }

    private static void PrintDirectoryTree(
        DirectoryInfo directory, int currentLevel)
    {
        var indentation = string.Empty;
        for (var i = RootLevel; i < currentLevel; i++)
        {
            indentation += Tab;
        }

        Console.WriteLine($"{indentation}-{directory.Name}");
        var nextLevel = currentLevel + 1;
        try
        {
            foreach (var subDirectory in directory.GetDirectories())
            {
                PrintDirectoryTree(subDirectory, nextLevel);
            }
        }
        catch (UnauthorizedAccessException e)
        {
            Console.WriteLine($"{indentation}-{e.Message}");
        }
    }
}

Este código es algo más complicado que el mínimo para completar esta tarea, ya que incluye la verificación de excepciones para manejar cualquier problema al obtener los directorios. A continuación encontrará un desglose del código en segmentos más pequeños con explicaciones de cada uno.

Main :

El método principal toma una entrada de un usuario como una cadena, que se utiliza como la ruta al directorio raíz. Luego llama al método PrintDirectoryTree con esta cadena como parámetro.

PrintDirectoryTree(string) :

Este es el primero de los dos métodos que manejan la impresión real del árbol de directorios. Este método toma una cadena que representa la ruta al directorio raíz como un parámetro. Comprueba si la ruta es un directorio real y, de no ser así, lanza una excepción DirectoryNotFoundException que luego se maneja en el bloque catch. Si la ruta es un directorio real, un DirectoryInfo objeto rootDirectory se crea de la trayectoria, y la segunda PrintDirectoryTree método se llama con el rootDirectory objeto y RootLevel , que es una constante con un valor de cero entero.

PrintDirectoryTree(DirectoryInfo, int) :

Este segundo método maneja la peor parte del trabajo. Toma un DirectoryInfo y un entero como parámetros. DirectoryInfo es el directorio actual y el entero es la profundidad del directorio en relación con la raíz. Para facilitar la lectura, la salida se sangra para cada nivel en que se encuentra el directorio actual, de modo que la salida se vea así:

-Root
    -Child 1
    -Child 2
        -Grandchild 2.1
    -Child 3

Una vez que se imprime el directorio actual, se recuperan sus subdirectorios, y luego se llama a este método en cada uno de ellos con un valor de nivel de profundidad de uno más que el actual. Esa parte es la recursión: el método que se llama a sí mismo. El programa se ejecutará de esta manera hasta que haya visitado todos los directorios del árbol. Cuando llegó a un directorio sin subdirectorios, el método volverá automáticamente.

Este método también detecta una UnauthorizedAccessException , que se produce si alguno de los subdirectorios del directorio actual está protegido por el sistema. El mensaje de error se imprime en el nivel de sangría actual para mantener la coherencia.

El método a continuación proporciona un enfoque más básico para este problema:

internal static void PrintDirectoryTree(string directoryName)
{
    try
    {
        if (!Directory.Exists(directoryName)) return;
        Console.WriteLine(directoryName);
        foreach (var d in Directory.GetDirectories(directoryName))
        {
            PrintDirectoryTree(d);
        }
    }
    catch (Exception e)
    {
        Console.WriteLine(e.Message);
    }
}

Esto no incluye la comprobación de errores específica o el formato de salida del primer enfoque, pero efectivamente hace lo mismo. Como solo usa cadenas en lugar de DirectoryInfo , no puede proporcionar acceso a otras propiedades de directorio como permisos.

Secuencia Fibonacci

Puedes calcular un número en la secuencia de Fibonacci usando la recursión.

Siguiendo la teoría matemática de F (n) = F (n-2) + F (n-1), para cualquier i> 0,

// Returns the i'th Fibonacci number
public int fib(int i) {
    if(i <= 2) {
        // Base case of the recursive function.
        // i is either 1 or 2, whose associated Fibonacci sequence numbers are 1 and 1.
        return 1;
    }
    // Recursive case. Return the sum of the two previous Fibonacci numbers.
    // This works because the definition of the Fibonacci sequence specifies
    // that the sum of two adjacent elements equals the next element.
    return  fib(i - 2) + fib(i - 1);
    
}

fib(10); // Returns 55

Calculo factorial

El factorial de un número (indicado con!, Como por ejemplo 9!) Es la multiplicación de ese número con el factorial de uno más bajo. Así, por ejemplo, 9! = 9 x 8! = 9 x 8 x 7! = 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1.

Así en el código que se convierte, usando la recursión:

long Factorial(long x)
{
    if (x < 1)
    {
        throw new OutOfRangeException("Factorial can only be used with positive numbers.");
    }

    if (x == 1)
    {
        return 1;
    } else {
        return x * Factorial(x - 1);
    }
}

Cálculo de PowerOf

El cálculo de la potencia de un número dado también se puede hacer recursivamente. Dado un número base n y un exponente e , debemos asegurarnos de dividir el problema en partes reduciendo el exponente e .

Ejemplo teórico:

• 2² = 2x2
• 2³ = 2x2x2 o, 2³ = 2² x 2
  Ahí radica el secreto de nuestro algoritmo recursivo (ver el código a continuación). Se trata de tomar el problema y separarlo en pequeños y más simples para resolver los trozos.
• Notas
  • cuando el número base es 0, debemos estar conscientes de devolver 0 como 0³ = 0 x 0 x 0
  • cuando el exponente es 0, debemos ser conscientes de devolver siempre 1, ya que esta es una regla matemática.

Ejemplo de código:

public int CalcPowerOf(int b, int e) {
    if (b == 0) { return 0; } // when base is 0, it doesn't matter, it will always return 0
    if (e == 0) { return 1; } // math rule, exponent 0 always returns 1
    return b * CalcPowerOf(b, e - 1); // actual recursive logic, where we split the problem, aka: 2³ = 2 * 2² etc..
}

Pruebas en xUnit para verificar la lógica:
Aunque esto no es necesario, siempre es bueno escribir pruebas para verificar su lógica. Los incluyo aquí escritos en el marco de xUnit .

    [Theory]
    [MemberData(nameof(PowerOfTestData))]
    public void PowerOfTest(int @base, int exponent, int expected) {
        Assert.Equal(expected, CalcPowerOf(@base, exponent));
    }

    public static IEnumerable<object[]> PowerOfTestData() {
        yield return new object[] { 0, 0, 0 };
        yield return new object[] { 0, 1, 0 };
        yield return new object[] { 2, 0, 1 };
        yield return new object[] { 2, 1, 2 };
        yield return new object[] { 2, 2, 4 };
        yield return new object[] { 5, 2, 25 };
        yield return new object[] { 5, 3, 125 };
        yield return new object[] { 5, 4, 625 };
}