Please navigate to the bottom of the page for Table of Contents

Sunday, May 15, 2011

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.

11 comments:

  1. very good explanation.A little observation for the GCD code, the last line should be :
    Gcd(number2, remainder);
    and not
    return Gcd(number2, remainder);

    ReplyDelete
    Replies
    1. ....no. Otherwise nothing would ever get returned.

      Delete
  2. Mayuran:

    The code GDC is correct in the article.

    There is a minor mistake in the GenerateFibonacci() function as it doesn't take fib(0) = 0 case.

    private static int Fibonacci(int x)
    {
    if (x <= 0)
    return 0;
    else if (x == 1)
    return 1;
    else
    return Fibonacci(x - 1) + Fibonacci(x - 2);
    }

    ReplyDelete
  3. number1 must be bigger than number2 otherwise won't work....

    ReplyDelete
  4. THanks Nikhil - nice explanation. The factorial is a really common question, I was asked it at Amazon interview too. I was looking around for a more challenging recursion interview question and I found this one:


    http://www.programmerinterview.com/index.php/general-miscellaneous/nested-list-recursion/

    ReplyDelete
  5. My Gcd runs faster than yours (:-)

    public static int Gcd2(int x, int y)
    {
    if (x==y) return x;
    return( Gcd2( Math.min(x, y), (Math.max(x,y)- Math.min(x,y)) ));
    }
    ambrooks1@gmail.com

    ReplyDelete
  6. You fibonacci code is wrong, 2 would return 2 not 1. you need if(n == 0) return 0;

    ReplyDelete
  7. GCD would fail if the 2nd number is 0.

    ReplyDelete
    Replies
    1. public static int Gcd(int number1, int number2)
      {
      if (number2 == 0)
      return number1;
      else // recurse
      return Gcd(number2, number1 % number2);
      }

      Delete