Recursion in Java

Definition : Recursion is a part of algorithms in which function calling itself until some base condition is not occur.

If any base condition is not found then function will run infinite times until the stack overflow is not occur.

So thinking about base case is the most important part of recursion.

What is base condition in recursion?
In the recursive program, the solution to the base case is provided and the solution of the bigger problem is expressed in terms of smaller problems.

static int sum(int n) {
if(n == 1) // base condition
return 1;

return n + sum(n-1);
}

In the above example, base case for n < = 1 is defined and larger value of number can be solved by converting to smaller one till base case is reached.

There are just 3 steps to solve a problem using Recursion:

1. Base Case: Think of the simplest possible input for the function.
2. Find the relation: Think how the larger can be solved with the help of the function of the smaller problem.
3. Generalise: Make a generalised function that solves the problem. Put all this togehter into Mathematical function or a tree.

How a particular problem is solved using recursion?
The idea is to represent a problem in terms of one or more smaller problems, and add one or more base conditions that stop the recursion. For example, we compute sum of n natural numbers if we know sum of (n-1). The base case for sum of n natural numbers would be n = 1. We return 1 when n = 1 as we discussed above.

Let us take the example how recursion works by taking a simple function.

Find the sum of n natural numbers:

package recursion;

public class SumOfNNaturalNumbers {
	
	static int sum(int n) {
		/* base case */
		if(n == 1) {
			return 1;
		} /* dividing problem into smaller problem by using recursion */
		return n + sum(n-1);
	}

	public static void main(String[] args) {
		System.out.println(sum(100));

	}

}

Output: 5050

So i hope friends you all understand the concept of recursion.

Happy Coding , Happy learning and think recursively….!

Stay tuned friends.. Thank You.