Recursion is an approach to solving algorithms by using a function that calls itself. This process in which a function calls itself is called recursion, and the function that calls itself is called a recursive function.

How does recursion work?

Every time the recursive function is called, the main problem is reduced into a sub-problem. The recursion continues until the sub-problem can be solved without calling the recursive function. This is called the base condition.

Hence, a recursive function must have two conditions to prevent an infinite loop

1. Base condition - where the answer can be derived without calling the recursive function. This is how a recursive function terminates the loop in which it calls itself.

2. Recursive condition - Condition that reduces the problem into a sub-problem and calls the recursive function.

Problems that can be solved using recursion

Many problems can be effectively solved using recursion. Some examples are Towers of Hanoi, Tree traversals, DFS of graphs etc.

public int factorial(int n) {
 //base condition
 if (n==0) {
  return 1;
 } else {
  //recursion
  return n*factorial(n-1);
 }
}

function fibonacci(int n) {
 //base condition
 if (n <= 2) {
  return 1;
 }
 //recursion
 return fibonacci(n — 1) + fibonacci(n — 2);
}