Java Programming Tutorial: Recursion in Java With Examples of Recursive Methods
What is Recursion?
Recursion may be defined as, “the process of invoking (and restarting) the same method that is currently executing is called Recursion”.
Another Definition of Recursion – Recursion in Java
A programming technique in which a method calls it self is known as recursion. A method that calls itself is called a Recursive method. The recursion is a powerful problem solving technique used in programming languages.
Advantages of using Recursion
- The use of recursion makes method simpler and shorter.
- Recursive methods are easy to write.
- Recursion is a problem-solving technique and it is an alternative to loops. Recursion provides you another way to solve problems that involve repetition, such as the problem of calculating factorial of a number.
- It is based on the concept of solving a problem by reducing the problem to smaller sub-problems.
- Recursive algorithms are simple so they are easy to understand
- Recursive algorithms are easy to implement
Limitation of Recursion
- The recursive methods are easy to write, but they are less efficient and do not perform well as compared to iteration. On the other hand, the iterative methods are difficult to write but they are more efficient and perform better as compared to recursion.
- Recursion repeatedly invokes the recursive method itself mechanism, and consequently the overhead, of method calls. Therefore, recursion may be expensive in both, memory space as well as processor time.
The Base Case and Recursive Case in Recursive Methods
There are two basic cases in any problem that can be solved using recursion technique as follows:
The Base Case: Recursion in Java
A base case is that part of a recursive method that does not contain a recursive call. Actually, it serves to limit or bound the process of repetition. Therefore, it terminates the process of recursion at some proper stage later during execution. Hence, there must be a special case to handle the simplest computations in the problem. This is called the base case for recursive problem.
Example of Base case:
Consider the recursive solution to factorial of a number problem. In this case, the base case will be: ” if number is zero then factorial is one”. We transform this in if statement of Java programming language as:
if ( number == 0)
Recursive Case: Recursion in Java
A recursive case is that part of a recursive method that does involve a recursive call. But every recursive call must simplify the computation in some way.
Example of Recursive Case
Let us consider the factorial problem. So, here the recursive case is “when n is greater than 0 , then factorial is calculated as n * factorial(n-1).
Therefore, the if else statement in factorial problem representing base case and recursive case will be as follows:
if ( n == 0) return 1; else return n * factorial(n-1);
Since we know from mathematics, n! = n x (n-1)!.
Hence we can say that 3! = 3 x (3-1)! therefore 3!= 3 x 2!
Similarly 2! = 2 x (2-1)! therefore 2! = 2 x 1 !
In addition, 1!= 1 * (1-1)! , therefore 1! = 1 x 0! and we know that 0! =1 which is our base case. Therefore, This will give us answer of 1!=1. We will put it in 2! = 2 x 1! to get 2. We will use it in 3!=3 x 2! to get answer of 3! = 3 x 2 =6.
Further more, the source code for recursive method factorial is as shown below:
Can You Think About How Does Recursion Work To Solve Factorial Problem when call is factorial(3).
Now a detailed table view of the recursion process for a call factorial(3) is shown in figure one on top of this article. Therefore scroll up please! Since this will be helpful for clear understanding.