Finite and Infinite Recursion with Examples in Java

Recursion is the process by which a function calls itself, either directly or indirectly, and the associated function is known as a recursive function. Recursion makes it easy to solve some difficulties. Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS, and other issues are examples of the problems that can be solved using the Recursion.

Types of Recursions:

Two different kinds of recursion can be distinguished based on when they terminate:

1. Finite Recursion
2. Infinite Recursion

Finite Recursion:

A finite number of recursive calls is required for the recursion to end, which is known as finite recursion. When a base condition is satisfied, a recursion comes to an end. It makes sure the function ends when its task is completed.

Implementation:

FileName: FiniteRecursionExample.java

Output:

 5 4 3 2 1 

Complexity Analysis:

The time complexity is O(N), and the space complexity of the above code is O(N)

Infinite Recursion:

When the recursion continues after a finite number of recursive calls, it is known as infinite recursion. The recursion continues indefinitely since the base condition is never satisfied. The program will then keep making recursive calls until a StackOverflowError occurs as an output.

Implementation:

FileName: InFiniteRecursionExample.java

Output:

 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 

Complexity Analysis:

The time complexity is non-finite since the recursion will never end, and the space complexity of the above code is non-finite.