Recursion

Recursion

Recursion is a process in which a function calls itself directly or indirectly. It’s a technique used to solve problems by breaking them down into smaller, more manageable sub-problems. A recursive function must have a base case or stopping criteria to avoid infinite recursion.

Backtracking

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time (by time, here, is referred to the time elapsed till reaching any level of the search tree).

Examples

The Factorial

In mathematics, the factorial of a non-negative integer, denoted by n!, is the product of all positive integers less than or equal to n. For example, the factorial of 3 represents the multiplication of numbers 3, 2, 1, i.e 3! = 3 × 2 × 1 and is equal to 6.

Let's implement it with recursion:

 
    Console.WriteLine(Factorial(3));

public partial class Program 
{

    public static int Factorial(int number)
    {
        if (number < 1)
        {
            return 1;
        }

        return number * Factorial(number - 1);

    }
}

Complexity

• Time complexity: O(N)

• Space complexity: O(1)

The Fibonacci series

In the Fibonacci series, each number is the sum of the two preceding ones. For an example: 0,1,1,2,3,5,8,13,21.

Let's implement it with recursion:

for (int i = 0; i < 5; i++)
{
    Console.WriteLine(Fibonacci(i));
}



public partial class Program 
{
    public static int Fibonacci(int number)
    {

        if (number < 2)
        {
            return number;
        }

        return Fibonacci(number - 1) + Fibonacci(number - 2);
    }
}

Complexity

• Time complexity: O(2^N)

• Space complexity: O(1)

As we know, O(2^N) time complexity is not good as per performance prospactive. Can we improve it? Yes, we can with the help of dynamic programming (Memoization/Caching). For an example:

for (int i = 0; i < 10; i++)
{
    Console.WriteLine(Fibonacci(i));
}



public partial class Program 
{
    private static Dictionary<int, int> fibonacci = new();
    public static int Fibonacci(int number)
    {
        if (number < 2)
        {
            return number;
        }

        // check result in cache
        if (fibonacci.ContainsKey(number))
        {
            return fibonacci[number];
        }

        var result =  Fibonacci(number - 1) + Fibonacci(number - 2);
        fibonacci[number] = result;
        return result;
    }
}

Complexity

• Time complexity: O(N). This is because the function only computes each Fibonacci number once due to memoization.

• Space complexity: O(N). This is because the algorithm uses a dictionary to store the Fibonacci numbers, and the size of this dictionary grows linearly with n, the number of numbers generated.

NOTE: Always cache repetitive steps data.