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.



Categories: JAVA

Tags: , , , , , , , , , , , , ,

9 replies

Trackbacks

  1. Merge Sort in Java – THE NUCLEAR GEEKS
  2. Palindrome of String Using Recursion – THE NUCLEAR GEEKS
  3. Tower of Hanoi Using Recursion – THE NUCLEAR GEEKS
  4. Tree: Inorder Traversal Hackerrank Solution – THE NUCLEAR GEEKS
  5. Tree: Preorder Traversal Hackerrank Solution – THE NUCLEAR GEEKS
  6. Tree: Postorder Traversal Hackerrank Solution – THE NUCLEAR GEEKS
  7. Vertical Order Traversal In Binary Tree – THE NUCLEAR GEEKS
  8. Tree: Binary Search Tree (BST) – THE NUCLEAR GEEKS
  9. Tree: Deletion Of Node In Binary Search Tree (BST) – THE NUCLEAR GEEKS

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: