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)
// 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 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)
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.