## Introduction to Recursive Function in Java

A Recursive function is the one that calls itself one or many times. A recursive function is used in situations where the same set of operations needs to be performed again and again till the result is reached. It performs several iterations and the problem statement keeps becoming simpler with each iteration.

Always a base limit has to be specified while writing a recursive function else it results in Stack Overflow error. A stack is a memory area reserved to maintain method invocations. The error is because the function starts executing continuously as it will not be able to find the limiting condition and hence finally exhausting the allocated memory. So to prevent Stack Overflow we define certain base conditions with the help of “if…else” statements (or any other conditional statements) which makes the recursion function to stop as soon as the required computation is completed.

### Types of Recursion in Java

There are 2 types of recursion in Java. They are:

#### 1. Direct Recursion

**Syntax: **

Here the function1 calls itself continuously hence is a recursive function.

`public static void main(String[] args){`

//few lines of code

function();

//few lines of code

}

function() {

//few lines of code

function();

//few lines of code

}

**Example**

Factorial of a number is an example of direct recursion. The basic principle of recursion is to solve a complex problem by splitting into smaller ones. For example, in the case of factorial of a number we calculate the factorial of “i” if we know its factorial of “i-1”.

4.8 (4,371 ratings)

View Course

**Code:**

`public class Factorial {`

static int fact(int i){

if (i == 1)

return 1;

else

return(i * fact(i-1));

}

public static void main(String[] args) {

System.out.println("The factorial of given number 6 is: "+fact(6));

}

}

**Output:**

#### 2. Indirect/Mutual Recursion

A function1 which calls another function2, which in-turn calls function1 either directly or indirectly is called an indirect recursive function.

**Syntax:**

Consider 2 functions called function1() and function2(). Here function1 calls function2 and function2 calls function1.

`function1(){`

//few lines of code

function2();

//few lines of code

}

function2(){

//few lines of code

function1();

//few lines of code

}

**Example**

To show indirect recursion, we take the following program used to find out if a given number is even or odd from the given input.

**Code:**

`import java.util.Scanner;`

public class IndirectRecursion {

public static boolean oddNum(int i) {

if (i<0) throw new IllegalArgumentException("Number is negative");

if(i == 0){

return false;

} else {

return evenNum(i-1);

}

}

public static boolean evenNum(int i) {

if (i<0) throw new IllegalArgumentException("Number is negative");

if(i == 0){

return true;

} else {

return oddNum(i-1);

}

}

public static void main(String[] args) {

Scanner inputNum = new Scanner(System.in);

System.out.print("Give a number: ");

int n = inputNum.nextInt();

if (evenNum(n)) System.out.println(n + " is even");

else System.out.println(n + " is odd");

inputNum.close();

}

}

**Output:**

### Examples of Recursion in Java

Here are some more examples to solve the problems using the recursion method.

#### Example #1 – Fibonacci Sequence

A set of “n” numbers is said to be in a Fibonacci sequence if number3=number1+number2 i.e. each number is a sum of its preceding two numbers. Hence the sequence always starts with the first two digits like 0 and 1. The third digit is a sum of 0 and 1 resulting in 1, the fourth number is the addition of 1 and 1 resulting in 2, and the sequence goes on.

Check out the following code in Java to generate a Fibonacci sequence:

`public class FibonacciSeries{`

static int num1=0,num2=1,num3=0;

static void fibonacci(int n){

if(n>0){

num3 = num1 + num2;

num1 = num2;

num2 = num3;

System.out.print(" "+num3);

fibonacci(n-1);

}

}

public static void main(String args[]){

int n=10;

System.out.print(num1+" "+num2);//printing constant first two digits 0 and 1

fibonacci(n-2);//Since first two numbers are already done

}

}

**Output:**

Here the first two numbers are initialized to 0 and 1 and printed. The variables “num1”, “num2” and “num3” is used to generate the required sequence. Variable “num3” is got by adding “num1” and “num2” and the numbers are shifted one position to the left by shuffling as shown in the code. The function “Fibonacci” is recursively called here and at each iteration, the value of “n” is decreased by 1. Hence the recursion exits as soon as “n” reaches value 0.

#### Example #2 – Tower Of Hanoi

This is a classic mathematical problem which is having 3 poles and “n” number of disks with different sizes. The puzzle goes as follows:

In the beginning, the first pole will be having the disks arranged such that the biggest disc of them all is at the bottom and the smallest one at the top of the pole. The objective is to move these disks from the first pole to third pole keeping the disks in the same position as that in the first. Following are a few conditions to keep in mind while shifting these disks:

1. At a time only one disk has to be moved.

2. In the process, placing a larger disk over a smaller one is not allowed.

3. The second (middle) pole can be used to mediate while transferring the discs from first to the second pole.

Following is the Java code which can be used to solve the puzzle:

**Code:**

`public class TowerOfHanoi {`

public static void main(String[] args) {

int count = 3;

tower(count, 'A', 'B', 'C');

}

public static void tower(int first, char disk1, char temp, char disk2) {

if (first == 1) {

System.out.println("Disk 1 from " + disk1 + " to " + disk2);

} else {

tower(first - 1, disk1, disk2, temp);

System.out.println("Disk " + first + " from " + disk1 + " to " + disk2);

tower(first - 1, temp, disk1, disk2);

}

}

}

**Output:**

Here the variable “count” represents the number of discs to be used. The function “tower” is the recursive function used to move the discs from rod 1 to rod 3. A simple solution to this problem can be provided by considering 2 discs at first.

- First, we start by moving disc1 from rod 1 to rod 2.
- Next, we move disc2 to rod 3.
- Finally, we finish by moving disc1 to rod 3 completing the required solution.

This same principle is applied for the “n” number of discs by moving (n-1)the disc from rod 1 to 2 and following similar steps as above.

### Advantages of Recursion in Java

- The code is easy to write and maintain.
- The best method to find the results where a large number of iterations are required.

### Disadvantages of Recursion in Java

- Recursive functions use more memory. This is because each time a recursive function is called; memory allocation is done newly for the variables on the stack. And the respective memory allocation is freed as soon as the variable values are returned.
- This process of memory allocation takes more time hence the execution is usually slow.

### Conclusion

Recursive functions are relatively simpler to code but they are also not that efficient as compared to the other existing methods. Hence they are majorly used in cases where the time given for development is less and also where a significant pattern can be observed in the problem.

### Recommended Articles

This is a guide to Recursion in Java. Here we discuss the types of Recursion in Java along with its different examples with the advantages and disadvantages. You may also look at the following articles to learn more-