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.

18 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
  8. GCD's program has error of stack overflow Exception
    when supplying values like 5 and 4 or 5 and 3,
    and can be solved as
    public int GCD(int num1, int num2)
    {
    int reminder = num1 % num2;
    if (reminder == 0)
    return num2;
    else
    {
    num1 = num2;
    num2 = reminder;
    return GCD(num1, num2);
    }
    }

    ReplyDelete
  9. The blog or and best that is extremely useful to keep I can share the ideas of the future as this is really what I was looking for, I am very comfortable and pleased to come here. Thank you very much.
    animal jam | five nights at freddy's | hotmail login

    ReplyDelete
  10. I usually ask during coding interviews a question about recursion: http://www.codeavenger.com/2017/04/26/Ask-about-recursion-during-coding-interviews-to-identify-good-talent.html

    ReplyDelete
  11. you can use iteration too

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

    ReplyDelete
  12. Who actually uses recursion in real life?

    ReplyDelete
  13. Nice and good article.. it is very useful for me to learn and understand easily.. thanks for sharing your valuable information and time.. please keep updating.more php jobs in hyderabad.

    ReplyDelete