1. What is recursion? Explain with examples and discuss when recursion is preferred over iteration.
Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. Each recursive call works on a simpler version of the original problem until reaching a base case that can be solved directly. The essential components of recursion are the base case which is the simplest scenario that can be solved without recursion and stops the recursive calls, and the recursive case which breaks the problem into smaller instances and makes recursive calls. Each recursive call should move closer to the base case, and the function combines results from recursive calls to solve the original problem. A simple example is calculating factorial. Factorial of n is defined as n times factorial of n minus 1, with base case factorial of 0 or 1 equals 1. This naturally maps to a recursive function. Another example is the Fibonacci sequence where each number is the sum of the two preceding ones. The base cases are F of 0 equals 0 and F of 1 equals 1. The recursive case is F of n equals F of n minus 1 plus F of n minus 2. How recursion works internally involves the call stack. When a function calls itself, the current execution state including parameters and local variables is saved on the call stack. The recursive call executes as a new function invocation. When a recursive call completes, its result is returned and the previous state is restored from the stack. The stack unwinds as recursive calls return, eventually returning to the original caller. Advantages of recursion include code simplicity and elegance for naturally recursive problems like tree traversal and divide-and-conquer algorithms. It provides a clear mathematical correspondence for problems defined recursively. It eliminates complex loop logic and state management. Some algorithms like tree and graph traversal are more naturally expressed recursively. Disadvantages include performance overhead as function calls have overhead and recursion can be slower than iteration. Each recursive call consumes stack space which can lead to stack overflow for deep recursion. There is redundant computation in naive recursive solutions like Fibonacci calculating same values repeatedly. Debugging can be harder as the call stack becomes complex. Use recursion when the problem has a recursive structure like trees, graphs, or divide-and-conquer algorithms. Use it when the recursive solution is significantly clearer than iterative as in tree traversal or backtracking. Use it when the recursion depth is manageable and will not cause stack overflow. Use it when the problem naturally divides into smaller similar subproblems. Examples include tree and graph traversal, divide-and-conquer algorithms like Merge Sort and Binary Search, backtracking problems like N-Queens and Sudoku, dynamic programming when combined with memoization, and problems involving recursive data structures. Use iteration when performance is critical and recursion overhead matters, when recursion depth could cause stack overflow, when the iterative solution is equally clear or clearer, and when space complexity needs to be minimized. Many recursive algorithms can be converted to iterative using explicit stacks or queues.