Recursion in Java

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:

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 :

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

Output :

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

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

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

 


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:

  • Fn = F(n-1) + F(n-2)
  • F1 = 1
  • F0 = 1

Output :

  • 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:

Recursion tree for fibonacci numbers.
Recursion tree for fibonacci numbers.

 


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:

Recursion diagram for factorial function
Recursion diagram for factorial function

 


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 :

Output :


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:

  • A recursive method takes more memory : 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.
  • It may cause Stack Exhaustion : If a method has large recursion depth, it may consume all the available memory.

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.

Output :


Here is the same example using a loop:

 


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:

  • 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.