The process in which a method calls itself is called ** recursion**, and the method that calls itself is a recursive method.

# 1. Syntax

A recursive method has one or more call to the method itself inside the method body:

1 2 3 4 5 |
access_modifier return_type method_name(param-list){ // Some Statements // Call to method_name(arg_list) // Some Statements } |

You have a set of normal Java statements and among them there is a call to this method itself. Apart from calling itself the method can have calls to other methods as well.

# 2. An Example

The factorial function is defined as :

for n>0*fact(n) = n* fact(n-1)*for n=0*fact(0) = 1*

1 2 3 4 5 6 7 8 9 10 11 12 13 |
public class Factorial_demo { // Definition of factorial function public static int factorial(int n){ if(n == 0){ return 1; // Base case : Terminating condition } else { return n * factorial(n-1); // General case : Recursive call } } public static void main(String[] args){ System.out.println("factorial(5) = " + factorial(5)); } } |

Output :

1 |
factorial(5) = 120 |

In the example above factorial function calls itself inside its body. factorial(5) calls factorial(4) which again calls factorial(3) and so on. Finally factorial(1) calls factorial(0) and the terminating condition is reached.

# 3. Two phases of recursion

Most recursive algorithms go through two phases

During this phase a method keeps calling itself again and again. The recursion depth increases during this phase.*Winding phase :*When method hits the terminating condition, it starts returning from the method calls and the recursion depth starts to decrease.*Unwinding Phase :*

Winding and Un-winding for factorial(5) can be visualized as:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Winding phase starts factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0) // Termination condition hit : Unwinding phase starts return 1 return 1*1 return 2*1 return 3*2 return 4*6 return 5*24 |

# 4. Multiple Recursion.

A method can have more than one recursive calls inside its body. Let’s have an example of a method with two recursive calls.

Fibonacci numbers are defined as:

**F**_{n}= F_{(n-1)}+ F_{(n-2)}**F**_{1}= 1**F**_{0}= 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class Fibonacci_demo { public static int fib(int n){ if(n==1 || n==0){ // Terminating condition return 1; } else { // Two recursive calls to the method itself. return fib(n-1) + fib(n-2); // Recursive Case } } public static void main(String[] args){ System.out.println("fib(0) = " + fib(0)); System.out.println("fib(1) = " + fib(1)); System.out.println("fib(2) = " + fib(2)); System.out.println("fib(3) = " + fib(3)); System.out.println("fib(4) = " + fib(4)); System.out.println("fib(5) = " + fib(5)); } } |

Output :

1 2 3 4 5 6 |
fib(0) = 1 fib(1) = 1 fib(2) = 2 fib(3) = 3 fib(4) = 5 fib(5) = 8 |

- Other common examples of multiple recursion include quick-sort, merge-sort etc.

# 5. Recursion Tree

When a method has more than one recursive call then those calls form a tree called as recursion tree. The recursion tree for fibonacci numbers from the previous example can be visualized as:

When a method has only one recursive call inside its body then the recursion diagram is a linear chain like structure. The recursion diagram for factorial function can be visualized as:

# 6. Depth of Recursion

Function calls made by a recursive method can be visualized as a tree. Depth of this recursion tree is defined as the depth of recursion for a method.

- Recursion depth for factorial(5) is 5.
- Recursion depth for fibonacci method, fib(5) is 4.

It is directly related to memory utilization of a method. A method with higher recursion depth takes more memory.

# 7. Common features of a Recursive method

By now you must have noticed two common features of any recursive method:

- Terminating Condition(also called base case) : A boolean condition to terminate the repeatitive function calls.
- Recursive call : The method calls itself.

# 8. Infinite Recursion

Most of the times you need to provide a terminating condition to exit the function call but it is not always necessary. Sometimes, it is desirable that a method keeps running.

Consider the example below that prints time in ** Hrs : Mins : Secs** format every second :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
import java.text.SimpleDateFormat; import java.util.Calendar; public class Infinite_demo { public static void print_time() { Calendar cal = Calendar.getInstance(); SimpleDateFormat sdf = new SimpleDateFormat("HH:mm:ss"); System.out.println( sdf.format(cal.getTime()) ); try{ Thread.sleep(1000); } catch (Exception E){ // Do nothing } print_time(); } public static void main(String[] args){ print_time(); } } |

Output :

1 2 3 4 5 6 7 8 |
12:34:25 12:34:26 12:34:27 12:34:28 12:34:29 12:34:30 12:34:31 ... |

# 9. Benefits of Recursion

- A recursive solution is intutive, concise, easier to write and understand.
- It is also easier to debug and maintain.
- Some problems are inherently recursive. In those situations, recursive solutions are quite natural. For example: Tower of Hanoi problem. You may write an iterative solution but it would be difficult to understand.

# 10. Drawbacks of Recursion

A recursive solution has some drawbacks as well:

When a method is called, new memory for variables of the method is allocated on the stack. This happens for every method call. When the method returns this memory is deallocated and available for reuse.*A recursive method takes more memory :*If a method has large recursion depth, it may consume all the available memory.*It may cause Stack Exhaustion :*

# 11. Recursion vs Iteration

Most of the time you can replace a recursive solution with some iterative solution.

- A recursive solution is implemented by function calls while an iterative solution is generally implemented using a loop.
- Most of the time, an iterative solution takes relatively less memory to do the same task.

Lets take a popular example of binary search algorithm using recursion and iteration. The algorithm searches a sorted array for a key and returns the index inside the array where it is found. If the key doesn’t exist inside the array it returns -1.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public class Recursive_binary_search_demo { // Searches for a key in a sorted array. // If found, it returns the index of the key, else it returns -1 public static int rec_binary_search(int[] arr, int l, int r, int key){ if(r >= l){ int mid = (l+r)/2; if(arr[mid] == key){ return mid; } else if(arr[mid] < key){ return rec_binary_search(arr, mid+1, r, key); } else{ return rec_binary_search(arr, l, mid-1, key); } } return -1; } public static void main(String[] args){ int[] arr = {3, 7, 11, 19, 22, 53, 54, 59, 73, 87, 97}; int index_of_19 = rec_binary_search(arr, 0, arr.length-1, 19); System.out.println("Index of 19 = " + index_of_19); } } |

Output :

1 |
Index of 19 = 3 |

Here is the same example using a loop:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public class Iterative_binary_search_demo { // Searches for a key in a sorted array. // If found, it returns the index of the key, else it returns -1 public static int itr_binary_search(int[] arr, int l, int r, int key){ while(r >= l){ int mid = (l+r)/2; if(arr[mid] == key){ return mid; } else if(arr[mid] < key){ l = mid+1; } else{ r = mid-1; } } return -1; } public static void main(String[] args){ int[] arr = {3, 7, 11, 19, 22, 53, 54, 59, 73, 87, 97}; int index_of_19 = itr_binary_search(arr, 0, arr.length-1, 19); System.out.println("Index of 19 = " + index_of_19); } } |

# 12. Tail Recursion

A method that has only one recursive call to itself and the recursive call is the last statement inside the method body is a tail recursive method.

For example the factorial method is a tail recursive method:

1 2 3 4 5 6 7 |
public static int factorial(int n){ if(n == 0){ return 1; } else { return n * factorial(n-1); // Single recursive call, Last call. } } |

- Tail recursive methods can be easily optimized by a compiler to take less memory.
- Most languages support tail recursion
**but as of now Java doesn’t support tail recursion.**

For more examples on recursion visit this link.