C# - Recursive Problem Solving

Recursive problem solving is a powerful technique in computer programming where a function calls itself to solve a problem by breaking it down into smaller, more manageable subproblems. It's often used for tasks that can be divided into identical or similar sub-tasks. In this example, I'll demonstrate recursive problem solving in C# with a classic example: calculating the factorial of a number.

1. Factorial Calculation:

In simple terms, the factorial of a number 'n' (written as n!) means you multiply all the positive numbers from 1 to 'n' together. For example, 5! equals 5 multiplied by 4, then multiplied by 3, then by 2, and finally by 1, (5*4*3*2*1) which equals 120.

C# Code Example

using System;

class Program
{
    static int CalculateFactorial(int n)
    {
        // Base case: If n is 0 or 1, return 1.
        if (n == 0 || n == 1)
        {
            return 1;
        }
        // Recursive case: Calculate factorial by calling the function with a smaller value.
        else
        {
            return n * CalculateFactorial(n - 1);
        }
    }

    static void Main()
    {
        int number = 5; // You can change this number to calculate the factorial for a different value.
        int result = CalculateFactorial(number);
        Console.WriteLine($"The factorial of {number} is {result}");
    }
}

Output

The factorial of 5 is 120

Illustration of Factorial Calculation:

1. The program defines a function called CalculateFactorial which takes an integer n as its parameter. This function calculates the factorial of n using recursion.
2. Inside the CalculateFactorial function:
   • It checks for a base case: If n is 0 or 1, it returns 1 because the factorial of 0 and 1 is 1.
   • If n is not 0 or 1 (i.e., the recursive case), it calculates the factorial of n by multiplying n with the result of a recursive call to CalculateFactorial(n - 1). This step breaks down the problem into smaller subproblems.
3. In the Main method:
   • It sets the number variable to 5 (you can change this value to calculate the factorial for a different number).
   • It calls the CalculateFactorial function with number as the argument and stores the result in the result variable.
   • Finally, it prints the result using Console.WriteLine, displaying a message indicating the factorial of the specified number.
4. When you run the program with number set to 5, it calculates the factorial of 5 by recursively calling CalculateFactorial as follows:
   • CalculateFactorial(5) calls CalculateFactorial(4).
   • CalculateFactorial(4) calls CalculateFactorial(3).
   • CalculateFactorial(3) calls CalculateFactorial(2).
   • CalculateFactorial(2) calls CalculateFactorial(1).
   • CalculateFactorial(1) returns 1 (base case).
   • As the recursion unwinds, each level multiplies its n value with the result from the previous level.
   • So, CalculateFactorial(2) returns 2 * 1 = 2, CalculateFactorial(3) returns 3 * 2 = 6, and so on.
   • Finally, CalculateFactorial(5) returns 5 * 6 = 30.
5. The program prints the result: "The factorial of 5 is 120," which is the calculated factorial of the specified number.

2. Merge Sort:

Merge Sort is a widely used sorting algorithm that employs the recursive problem-solving approach to divide and conquer the sorting task. In this example, I'll demonstrate how to implement Merge Sort in C# with a clear explanation and provide the complete source code along with the output.

Explanation of the Merge Sort Algorithm:

1. Merge Sort is a sorting technique that uses a divide-and-conquer strategy to sort an array or list of elements. It works as follows:
2. Divide: The original array is divided into smaller subarrays until each subarray contains only one element.
3. Conquer: These individual subarrays are then sorted.
4. Combine: Finally, the sorted subarrays are merged together to create a fully sorted array.

This process keeps happening over and over again until the whole array is arranged in order.

Code Example:

using System;

class MergeSort
{
    static void Main()
    {
        int[] arr = { 12, 11, 13, 5, 6, 7 };
        Console.WriteLine("Original Array:");
        PrintArray(arr);

        MergeSortAlgorithm(arr, 0, arr.Length - 1);
        
        Console.WriteLine("\nSorted Array:");
        PrintArray(arr);
    }

    // Merge two subarrays of 'arr'.
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    static void Merge(int[] arr, int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;

        int[] L = new int[n1];
        int[] R = new int[n2];

        // Copy data to temp arrays L[] and R[]
        for (int i = 0; i < n1; i++)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[m + 1 + j];

        // Merge the temp arrays back into arr[l..r]
        int k = l;
        int x = 0, y = 0;
        while (x < n1 && y < n2)
        {
            if (L[x] <= R[y])
            {
                arr[k] = L[x];
                x++;
            }
            else
            {
                arr[k] = R[y];
                y++;
            }
            k++;
        }

        // Copy the remaining elements of L[], if there are any
        while (x < n1)
        {
            arr[k] = L[x];
            x++;
            k++;
        }

        // Copy the remaining elements of R[], if there are any
        while (y < n2)
        {
            arr[k] = R[y];
            y++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using Merge()
    static void MergeSortAlgorithm(int[] arr, int l, int r)
    {
        if (l < r)
        {
            // Find the middle point
            int m = l + (r - l) / 2;

            // Sort the first and second halves
            MergeSortAlgorithm(arr, l, m);
            MergeSortAlgorithm(arr, m + 1, r);

            // Merge the sorted halves
            Merge(arr, l, m, r);
        }
    }

    // Utility function to print an array
    static void PrintArray(int[] arr)
    {
        foreach (int item in arr)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}

Output:

Original Array:
12 11 13 5 6 7

Sorted Array:
5 6 7 11 12 13

In this code, we use the Merge Sort algorithm to sort an array of integers. The MergeSortAlgorithm function recursively divides the array into smaller subarrays until each subarray has only one element. Then, the Merge function combines these sorted subarrays to create larger sorted subarrays until the entire array is sorted.

The output demonstrates the original unsorted array and the sorted array produced by the Merge Sort algorithm.