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.

23 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. Hi There,

      Amaze! I have been looking bing for hours because of this and i also in the end think it is in this article! Maybe I recommend you something helps me all the time?


      I am trying to scraping a web-site using Jsoup.

      I have Login successfully and while move to the next page (Result page) the data are loading by Restful web-service as JSON. need to pass the cookies and secret keeys too.

      12.Is it possible to read web-service using Jsoup?
      import java.util.*;

      public class AddStuff {
      public static double addUp(List addfrom) {
      double counter=0.0;
      for (Number n : addfrom) {
      counter+=n.doubleValue();
      }
      return counter;
      }
      public static void main(String[] args) {
      List addfrom = Arrays.asList(1,2,3,4,5,6,7,8,9,10);
      double sum=addUp(addfrom);
      System.out.println(sum);
      }
      }
      Great effort, I wish I saw it earlier. Would have https://asha24.com/blog/step-by-step-java-performance-tuning-methods
      saved my day :)


      Ciao,

      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. 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
  10. 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
  11. Who actually uses recursion in real life?

    ReplyDelete
  12. Pretty blog, so many ideas in a single site, thanks for the informative article, keep updating more article.
    PHP course in chennai

    ReplyDelete
  13. Nice blog has been shared by you. it will be really helpful to many peoples who are all working under the technology.thank you for sharing this blog.

    Php course in chennai

    ReplyDelete
  14. Hi Dear, have you been certainly visiting this site daily, if that's the case you then will certainly get good knowledge.
    business logo design company

    ReplyDelete
  15. Recursion is a fundamental programming concept that allows functions to call themselves. The Security Wordpess It's a powerful tool for solving complex problems by breaking them down into smaller, more manageable steps.

    ReplyDelete