Define :
- Recursion in java is a process in which a function call itself over, and over again, or in other words -
- Recursion is a process of expressing a function that calls itself to perform a specific operation.
- Suppose P is a procedure containing either a call statement to itself or a call statement to a second procedure that may eventually result in a call statement back to the original procedure P. Then P is called recursive procedure.
- Recursion avoids loop in a program.
- Performs better in solving problems based on tree structures. Like - Tower of Hanoi problem is more easily solved in recursion.
A recursive procedure must have the following two properties :
- There must be certain criteria, called base criteria, for which the procedure does not call itself.
- Each time the procedure does call itself, it must be closer to the criteria.
Syntax
|
returnType methodName() {
// method body...
// we can call a method using methodName with parenthesis.
methodName(); // method calling
}
|
Now we will understand recursion with the help of some examples -
Example 1 - Finding factorial of a number using resursion.
Output :
Example2 - Print fibonacci series using recursion -
|
//Fibonacci Series using Recursion
class T
{
static int fibonacci (int a)
{
if (a <= 1)
return a;
else
return fibonacci(a-1) + fibonacci(a-2);
}
public static void main (String args[])
{
int a = 5;
System.out.println(fibonacci(a));
}
}
|
Output :
Example 3 - we can see a simple example as printing a name certain number of times -
Output :
Advantages of Recursion
- Recursion adds clarity and (sometimes) reduces the time needed to write and debug code (but doesn't necessarily reduce space requirements or speed of execution).
- Reduces time complexity.
- Performs better in solving problems based on tree structures.
Disadvantages of Recursion
- It is usually slower due to the overhead of maintaining the stack.
- It usually uses more memory for the stack.
- Recursion isn't faster than loop, because loops have built-in support in CPUs, whereas recursion is implemented using the generally slower function call / return mechanism. That said, recursion can be made to be as fast as loops by a good compiler, when the code is properly written.
