C# Language
ricorsione

Osservazioni

Descrivere ricorsivamente una struttura dell'oggetto

La ricorsione è quando un metodo si chiama da solo. Preferibilmente lo farà finché non verrà soddisfatta una condizione specifica e quindi uscirà normalmente dal metodo, ritornando al punto da cui è stato chiamato il metodo. In caso contrario, potrebbe verificarsi un'eccezione di overflow dello stack dovuta a troppe chiamate ricorsive.

/// <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
    }
}

Ricorsione in inglese semplice

La ricorsione può essere definita come:

Un metodo che chiama se stesso finché non viene soddisfatta una condizione specifica.

Un esempio eccellente e semplice di ricorsione è un metodo che otterrà il fattoriale di un dato numero:

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

In questo metodo, possiamo vedere che il metodo prenderà un argomento, number .

Passo dopo passo:

Dato l'esempio, eseguendo Factorial(4)

1. Il number (4) == 1 ?
2. No? return 4 * Factorial(number-1) (3)
3. Poiché il metodo viene chiamato ancora una volta, ripete ora il primo passo utilizzando Factorial(3) come nuovo argomento.
4. Questo continua finché non viene eseguito Factorial(1) e number (1) == 1 restituisce 1.
5. Complessivamente, il calcolo "crea" 4 * 3 * 2 * 1 e infine restituisce 24.

La chiave per comprendere la ricorsione è che il metodo chiama una nuova istanza di se stesso. Dopo il ritorno, l'esecuzione dell'istanza chiamante continua.

Utilizzo della ricorsione per ottenere la struttura della directory

Uno degli usi della ricorsione consiste nel navigare attraverso una struttura gerarchica dei dati, come un albero di directory del file system, senza sapere quanti livelli ha l'albero o il numero di oggetti su ciascun livello. In questo esempio, vedrai come usare la ricorsione su un albero di directory per trovare tutte le sottodirectory di una directory specificata e stampare l'intero albero sulla console.

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}");
        }
    }
}

Questo codice è un po 'più complicato del minimo indispensabile per completare questa attività, poiché include il controllo delle eccezioni per gestire eventuali problemi con l'ottenimento delle directory. Di seguito troverai una suddivisione del codice in segmenti più piccoli con le spiegazioni di ciascuno.

Main :

Il metodo principale accetta un input da un utente come una stringa, che deve essere utilizzato come percorso della directory principale. Quindi chiama il metodo PrintDirectoryTree con questa stringa come parametro.

PrintDirectoryTree(string) :

Questo è il primo di due metodi che gestiscono la stampa dell'albero della directory effettiva. Questo metodo prende una stringa che rappresenta il percorso della directory root come parametro. Controlla se il percorso è una directory effettiva e, in caso contrario, genera una DirectoryNotFoundException che viene quindi gestita nel blocco catch. Se il percorso è una directory reale, una DirectoryInfo oggetto rootDirectory viene creato dal percorso, e la seconda PrintDirectoryTree metodo viene chiamato con il rootDirectory oggetto e RootLevel , che è un numero intero costante con un valore di zero.

PrintDirectoryTree(DirectoryInfo, int) :

Questo secondo metodo gestisce il peso del lavoro. Prende un DirectoryInfo e un intero come parametri. DirectoryInfo è la directory corrente e il numero intero è la profondità della directory relativa alla radice. Per facilità di lettura, l'output è indentato per ogni livello in profondità nella directory corrente, in modo che l'output assomigli a questo:

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

Una volta stampata la directory corrente, vengono recuperate le sottodirectory e questo metodo viene quindi chiamato su ciascuno di essi con un valore del livello di profondità superiore a quello corrente. Quella parte è la ricorsione: il metodo che si autodefinisce. Il programma verrà eseguito in questo modo finché non avrà visitato tutte le directory dell'albero. Quando ha raggiunto una directory senza subdirectory, il metodo restituirà automaticamente.

Questo metodo rileva anche una UnauthorizedAccessException , che viene generata se una delle sottodirectory della directory corrente è protetta dal sistema. Il messaggio di errore viene stampato al livello di indentazione corrente per coerenza.

Il metodo seguente fornisce un approccio più di base a questo 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);
    }
}

Questo non include lo specifico controllo degli errori o la formattazione dell'output del primo approccio, ma fa effettivamente la stessa cosa. Poiché utilizza solo stringhe anziché DirectoryInfo , non può fornire l'accesso ad altre proprietà di directory come le autorizzazioni.

Sequenza di Fibonacci

Puoi calcolare un numero nella sequenza di Fibonacci usando la ricorsione.

Seguendo la teoria matematica di F (n) = F (n-2) + F (n-1), per ogni 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

Calcolo fattoriale

Il fattoriale di un numero (indicato con!, Come per esempio 9!) È la moltiplicazione di quel numero con il fattoriale di uno inferiore. Quindi, per esempio, 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.

Quindi nel codice che diventa, usando la ricorsione:

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);
    }
}

Calcolo PowerOf

Il calcolo della potenza di un dato numero può essere eseguito in modo ricorsivo. Dato un numero base n ed esponente e , dobbiamo assicurarci di dividere il problema in blocchi diminuendo l'esponente e .

Esempio teorico:

• 2² = 2x2
• 2³ = 2x2x2 o, 2³ = 2² x 2
  Qui sta il segreto del nostro algoritmo ricorsivo (vedi il codice sotto). Si tratta di prendere il problema e separarlo in blocchi più piccoli e più semplici da risolvere.
• Gli appunti
  • quando il numero di base è 0, dobbiamo essere consapevoli di restituire 0 come 0³ = 0 x 0 x 0
  • quando l'esponente è 0, dobbiamo essere consapevoli di restituire sempre 1, in quanto questa è una regola matematica.

Esempio di codice:

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..
}

Test in xUnit per verificare la logica:
Sebbene ciò non sia necessario, è sempre consigliabile scrivere test per verificare la logica. Includo quelli qui scritti nel framework 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 };
}