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.

very good explanation.A little observation for the GCD code, the last line should be :

ReplyDeleteGcd(number2, remainder);

and not

return Gcd(number2, remainder);

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

DeleteHi There,

DeleteAmaze! 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,

Mayuran:

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

}

You are correct, i noticed this too.

Deletenumber1 must be bigger than number2 otherwise won't work....

ReplyDeleteno. Try 4 and 8.

DeleteTHanks 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:

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

My Gcd runs faster than yours (:-)

ReplyDeletepublic 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

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

ReplyDeleteGCD would fail if the 2nd number is 0.

ReplyDeletepublic static int Gcd(int number1, int number2)

Delete{

if (number2 == 0)

return number1;

else // recurse

return Gcd(number2, number1 % number2);

}

GCD's program has error of stack overflow Exception

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

}

}

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

ReplyDeleteyou can use iteration too

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

}

}

}

Who actually uses recursion in real life?

ReplyDelete• 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

ReplyDeleteAzure Online course BangalorePretty blog, so many ideas in a single site, thanks for the informative article, keep updating more article.

ReplyDeletePHP course in chennai

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.

ReplyDeletePhp course in chennai

Great Article

ReplyDeleteFInal Year Project Centers in Chennai

JavaScript Training in Chennai

JavaScript Training in Chennai

Great Blog to read,Its gives more useful information.Thank lot.

ReplyDeleteApache Spark Training in Pune

Spark Training Institute in Pune

Aivivu chuyên vé máy bay, tham khảo

ReplyDeletevé máy bay đi Mỹ khứ hồi

chuyến bay từ mỹ về việt nam hôm nay

ve may bay tu canada ve viet nam

gia ve may bay vietjet tu han quoc ve viet nam

Hi Dear, have you been certainly visiting this site daily, if that's the case you then will certainly get good knowledge.

ReplyDeletebusiness logo design company