Advanced Recursion Techniques in C#

Lesson Overview

Welcome to this most intriguing and yet somewhat confusing approach in the world of algorithms — recursion. Today, we will dive deep into Advanced Recursion Techniques. These techniques will not only broaden your understanding of the concept but also equip you with the ability to tackle complex problems comfortably. Recursion, simply put, is a method where the solution to a problem depends on smaller instances of the same problem. Advanced recursion techniques allow us to solve problems involving deep tree structures and backtracking, which are quite common in certain interview questions.

Quick Example

To give you a small taste of what's in store, let's take a look at a recursive function that generates all permutations of a list of numbers. The strategy here is to use a method known as backtracking. Backtracking is a general algorithm for finding all (or some) solutions to certain computational problems. In our example, we are recursively swapping all elements (for each index from the first to the last), moving one step further in the depth of the list after each recursion until we reach the end. Once we get there, we append the current state of the array to our results array.

using System;
using System.Collections.Generic;

public class Permutations
{
    public static void Main(string[] args)
    {
        Permutations perm = new Permutations();
        List<List<int>> result = perm.Permute(new int[] { 1, 2, 3 });
        foreach (var list in result)
        {
            Console.WriteLine(string.Join(", ", list)); 
        }
        // Output: 
        // 1, 2, 3
        // 1, 3, 2
        // 2, 1, 3
        // 2, 3, 1
        // 3, 2, 1
        // 3, 1, 2
    }

    public List<List<int>> Permute(int[] nums)
    {
        List<List<int>> result = new List<List<int>>();
        Backtrack(nums, 0, result);
        return result;
    }

    private void Backtrack(int[] nums, int first, List<List<int>> result)
    {
        if (first == nums.Length)
        {
            List<int> current = new List<int>();
            foreach (int num in nums)
            {
                current.Add(num);
            }
            result.Add(current);
        }
        for (int i = first; i < nums.Length; i++)
        {
            Swap(nums, first, i); // Swap numbers
            Backtrack(nums, first + 1, result);
            Swap(nums, first, i); // Swap them back to reset the state
        }
    }

    private void Swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal