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.

DeleteMayuran:

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

}

}