## 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.

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);

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

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.*;

double counter=0.0;
for (Number n : addfrom) {
counter+=n.doubleValue();
}
return counter;
}
public static void main(String[] args) {
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,

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);
}

1. You are correct, i noticed this too.

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

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/

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

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

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

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

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);
}
}

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

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;
}
}
}

12. Who actually uses recursion in real life?

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.

14. • 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 updatingAzure Online course Bangalore

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

16. 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