Recursion: Solves problems by breaking them into smaller, self-similar subproblems. Can be more elegant for some problems. | Iteration: Solves problems by repeating a block of code until a condition is met. Generally more efficient in terms of speed and memory.

Linear Search: Checks each element sequentially. Works on unsorted arrays. | Binary Search: Repeatedly divides the search interval in half. Requires a sorted array.

Iterative Binary Search: Uses loops to narrow the search space. More efficient in terms of memory usage. | Recursive Binary Search: Calls itself with smaller sub-arrays. Can be more concise and easier to read for some programmers.

In algorithms like tree traversal, graph searching, and in compilers for parsing code.

Searching for a word in a dictionary, finding a contact in a sorted list, or locating data in a sorted database index.

Used in external sorting (sorting large datasets that don't fit in memory), and as a building block in other algorithms.

1. Identify the base case(s). 2. Define the recursive call to solve a smaller subproblem. 3. Ensure the recursive call moves towards the base case.

1. Find the middle element. 2. Compare the target to the middle element. 3. If target equals middle, return index. 4. If target is less than middle, search the left half. 5. If target is greater than middle, search the right half. 6. Repeat until found or search space is empty.

1. Divide the array into two halves. 2. Recursively sort the two halves. 3. Merge the sorted halves.