| It is recomended that you learn recursion before this topic. |
|---|
What is recursion?
Recursion is a programming technique where a method calls itself to solve smaller versions of a problem.
A recursive method has two essential parts:
- Base Case: The condition under which the recursion stops.
- Recursive Case: The part where the method calls itself with a simpler or smaller input.
Example — Factorial (n!)
In the code above, factorial(0) returns 1 (base case), and otherwise, the method keeps calling itself with a smaller n.
All problems which can be solved with iteration (loops) can be solved with recursion. Are all problems that are solvable with recursion solvable with loops? - Stack Overflow
Recursive Searching
Binary Search (Recursive Version)
Binary Search efficiently finds a target value in a sorted array by repeatedly dividing the search interval in half. Its time complexity is O(log n). It requires that the array is sorted.
You can see an example of recursive Binary Search below:
A call to binarySearch returns the index of an element with value target in the array arr, between the indices of left and right.
The algorithm works in the following manner:
- It finds the middle (mid) index between left and right.
- If the target is at arr[mid], return mid.
- Otherwise, call binarySearch with indices left to mid - 1 if the target is smaller.
- The base case is if the left index is greater than the right index. In this case, we return -1.
Binary Search Algorithm – Iterative and Recursive Implementation | GeeksforGeeks
Recursive Sorting
Below you can see an example of how we can use recursion to sort an array:
Merge Sort is a divide and conquer algorithm:
- Split the array into halves.
- Recursively sort each half.
- Merge the sorted halves.
Java Program for Merge Sort | GeeksforGeeks
Recursion Menu
The Java program below demonstrates a simple use of recursion to implement a text-based menu. When the program runs, it displays a menu with three options, one of them being to exit. The user is prompted to enter a choice, and based on the input, the corresponding action is performed. After completing the selected action (unless the user chooses to exit), the menu() method calls itself recursively to display the menu again. This continues until the user selects the “Exit” option, at which point the recursion stops using a return statement, and the program ends. This approach illustrates how recursion can be used as an alternative to loops for repeating a task. It is a good demonstration of how you can use recursion instead of loops. Note: it is better to use loops for this application because recursion can overflow memory much faster.
