Recursion–concepts and code

Recursion is a simple yet powerful concept that has been around for some time in our lives. In simple terms, recursion is the process in which the function keeps calling itself (with possibly a different set of arguments) till some base condition is met. For a procedure to be truly recursive, it should have 2 parts – an end condition (a statement that returns a value) and one or more calls to itself. Let’s see this with a common example – factorial.

Find the factorial of a number using recursion

public static long Factorial(long number)
{
    // base condition - if the number is 0 or 1, return 1
    if (number <= 1)
        return 1;
    else
    {
        // recursive call to get the factorial again
        return number * Factorial(number - 1);
    }
}

As you can see in the above example, there is a base condition that allows the recursive call to terminate and then there is the recursive call itself. Let’s look at another example: Fibonacci sequence.

 

Fibonacci Sequence Generation using Recursion

The Fibonacci sequence is a classic example of recursion:

• Fib(0) is 0 [base case]
  
• Fib(1) is 1 [base case]
  
• For all integers n > 1: Fib(n) is (Fib(n-1) + Fib(n-2)) [recursive definition]

public static int GenerateFibonacci(int count)
{
    if (count <= 1)
        return 1;
    else
        return GenerateFibonacci(count - 1) + GenerateFibonacci(count - 2);
}

Apart from these 2 classic recursion problems, another one that I love to ask is how to find the GCD (greatest common divisor) of 2 numbers. For example, the GCD for 4 and 8 is 4, for 6 and 8 is 2, for 13 and 45 is 1 and so on. Let’s see how we can solve this using recursion.

Find Greatest Common Divisor (GCD) of 2 numbers using recursion

public static int Gcd(int number1, int number2)
{
    // find the remainder
    int remainder = number1 % number2;
    // base condition - if the number divide
    if (remainder == 0)
        return number2;
    else // recurse
        return Gcd(number2, remainder);
}

Recursion is a very powerful technique and extreme care should be exercised to make sure you have a valid base condition and the recursive call. If not coded properly, it is very easy to have stack overflow from recursion.