Top 50 Recursion Interview Questions

Introduction

Recursion is a powerful concept in computer science that involves solving problems by breaking them down into smaller, simpler instances of the same problem. In an interview, recursion questions often test your ability to think recursively and design efficient algorithms. These questions may ask you to solve problems like calculating factorials, finding Fibonacci numbers, or traversing tree structures. To approach recursion questions, remember to identify the base case (the simplest instance of the problem) and define the recursive step (how to break down the problem into smaller instances). Understanding recursion and practicing recursive thinking will help you tackle these interview questions with confidence.

Questions

1. What is recursion?

Recursion is a programming technique in which a function calls itself to solve a problem. It is a way to break down a complex problem into smaller, more manageable subproblems that are of the same nature as the original problem. The process continues until the base case is reached, which provides the stopping condition for the recursive calls.

2. What is a base case in recursion? Why is it important?

The base case in recursion is the condition that stops the recursive calls and provides the final result or value. It acts as a termination condition, preventing the function from infinitely calling itself and causing an infinite loop.

Example (Factorial using recursion in C++):

#include <iostream>

int factorial(int n) {
    if (n == 0) { // Base case: When n is 0, return 1
        return 1;
    } else {
        return n * factorial(n - 1); // Recursive call with a smaller subproblem
    }
}

int main() {
    int n = 5; // Example: Calculate factorial of 5
    int result = factorial(n);
    std::cout << "Factorial of " << n << " is: " << result << std::endl;
    return 0;
}

In this C++ code, the factorial function takes an integer n as input and calculates the factorial recursively. When n is 0, it returns 1 (base case). Otherwise, it calls itself with a smaller subproblem (n - 1) and multiplies the result with n to get the factorial of n. The main function demonstrates an example of calculating the factorial of 5 and prints the result.

3. What is the difference between recursion and iteration?

4. Explain the concept of recursive function calls in programming.

Recursive function calls occur when a function invokes itself within its own definition to solve a smaller version of the problem. Each recursive call creates a new instance of the function with its set of local variables and parameters. The recursive calls continue until the base case is reached, at which point the function starts to return values, and the recursion “unwinds” back to the original function call, providing the final result.

Example (Sum of integers using recursion in C++):

#include <iostream>

int sum_recursive(int n) {
    if (n == 0) {
        return 0; // Base case: When n is 0, return 0
    } else {
        return n + sum_recursive(n - 1); // Recursive call with a smaller subproblem
    }
}

int main() {
    int num = 5; // Example input value

    int result = sum_recursive(num);

    std::cout << "Sum of numbers from 1 to " << num << " is: " << result << std::endl;

    return 0;
}

In this C++ version of the code, we define the sum_recursive function that calculates the sum of numbers from 1 to n using recursion. The base case is when n becomes 0, and in that case, the function returns 0. Otherwise, the function makes a recursive call with a smaller subproblem, where n - 1 is passed as the argument. The recursive call continues until the base case is reached, and then the results are combined to calculate the final sum.

In the main function, we call sum_recursive with an example input value of num = 5 and print the result.

5. What is tail recursion? How is it different from non-tail recursion?

Tail recursion is a special case of recursion in which the recursive call is the last operation performed within the function before returning its result. It allows some programming languages and compilers to optimize memory usage by reusing the current function’s stack frame for the recursive call.

Non-tail recursion, on the other hand, involves additional computations or operations after the recursive call, which prevents the current stack frame from being reused and may lead to stack overflow in deeply nested recursive calls.

Example of tail recursion (Factorial with accumulator in C++):

#include <iostream>

int factorial_tail_recursive(int n, int acc = 1) {
    if (n == 0) {
        return acc; // Base case: When n is 0, return the accumulated result
    } else {
        return factorial_tail_recursive(n - 1, n * acc); // Tail recursive call with accumulator
    }
}

int main() {
    int n = 5;
    int result = factorial_tail_recursive(n);
    std::cout << "Factorial of " << n << " is: " << result << std::endl;
    return 0;
}

6. What is the stack overflow error in recursion? How can it be prevented?

A stack overflow error occurs when the call stack, which is used to manage function calls and store local variables and information, exceeds its size limit. This can happen in deeply nested or unbounded recursion where there are too many recursive function calls, and the available stack memory gets exhausted.

To prevent stack overflow errors in recursion, you can:

• Ensure that your base case is correct and will be reached eventually.
• Optimize tail-recursive functions, as some programming languages and compilers can perform tail call optimization to reuse stack frames.
• Convert the recursive solution to an iterative one, as iterative approaches often consume less memory than recursive ones.
• Use memoization or dynamic programming techniques to store and reuse intermediate results, reducing the need for repetitive recursive calls.

7. What are some practical applications of recursion in programming?

Recursion is widely used in programming and is particularly useful in solving problems that exhibit a recursive structure. Some practical applications of recursion include:

• Tree and graph traversals: Finding paths, searching, or performing operations on tree and graph data structures.
• File system navigation: Exploring directories and their subdirectories recursively.
• Mathematical calculations: Computing factorials, Fibonacci series, and combinations.
• Parsing and language processing: Building abstract syntax trees using recursive descent parsing.
• Backtracking algorithms: Solving puzzles like N-Queens, Sudoku, or finding all possible combinations.
• Divide and conquer algorithms: Sorting (e.g., merge sort, quicksort), binary search.

8. Explain how recursion can be used to solve problems related to tree and graph data structures.

Recursion is particularly useful for tree and graph-related problems because these data structures inherently have a recursive nature. Some common scenarios where recursion can be applied are:

• Tree traversals: Recursive approaches can be used for in-order, pre-order, and post-order tree traversals. When visiting a node, the same traversal function is called recursively on the left and right subtrees, allowing you to explore the entire tree.
• Graph traversals: Similar to tree traversals, recursive methods can be employed for depth-first search (DFS) in graphs. During the traversal, the function is called recursively on adjacent unvisited nodes until all nodes are explored.
• Pathfinding: Recursive algorithms like depth-first search can be used to find paths between nodes in a graph. By traversing the graph recursively, you can find paths from one node to another.
• Tree/Graph operations: Various operations on tree and graph structures, such as finding the height, checking if a tree is balanced, or finding cycles in a graph, can be solved using recursion.

9. Explain the process of converting a recursive function to an iterative function.

Converting a recursive function to an iterative function involves rewriting the logic using loops instead of function calls. This transformation can often lead to improved performance and memory usage.

The general steps for converting a recursive function to an iterative one are:

1. Identify the base case(s) and the recursive calls in the original function.
2. Create a data structure to mimic the call stack in the recursive function. This data structure will keep track of the intermediate values needed during the iteration.
3. Replace the recursive calls with a loop, and use the data structure to manage the state that would have been maintained on the call stack during recursion.
4. Update the loop until the equivalent result is obtained, ensuring the same logic as the original recursive function.

Here’s an example of converting the factorial function from recursion to iteration using a loop in C++:

Recursive version:

#include <iostream>

int factorial_recursive(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial_recursive(n - 1);
    }
}

int main() {
    int num = 5;
    int result = factorial_recursive(num);
    std::cout << "Factorial of " << num << " is: " << result << std::endl;
    return 0;
}

Iterative version:

#include <iostream>

int factorial_iterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

int main() {
    int n;
    std::cout << "Enter a number: ";
    std::cin >> n;
    int result = factorial_iterative(n);
    std::cout << "Factorial of " << n << " is: " << result << std::endl;
    return 0;
}

10. What are the advantages and disadvantages of using recursion in your code?

Advantages of using recursion:

• Readability: Recursive code can be more intuitive and easier to understand, especially for problems with a recursive nature.
• Conciseness: Recursive solutions can often be more concise, reducing the lines of code required.
• Divide and conquer: Recursion naturally breaks down complex problems into smaller, manageable subproblems.
• Certain problems are naturally suited for recursion, making the code more elegant and efficient.

Disadvantages of using recursion:

• Memory usage: Deeply nested recursion can lead to a large call stack, potentially causing a stack overflow error.
• Performance: Recursive solutions can be less efficient compared to iterative counterparts due to function call overhead.
• Difficult debugging: Debugging recursive code can be challenging because of multiple levels of function calls and potential infinite loops.
• May not be suitable for all problems: Some problems may have a more straightforward and efficient iterative solution.

11. In what scenarios is recursion generally a good approach? In what scenarios is it generally not a good approach?

Recursion is generally a good approach in scenarios where:

• The problem exhibits a recursive structure, such as tree or graph-related problems.
• Dividing the problem into smaller subproblems leads to a more elegant and readable solution.
• Backtracking or exhaustive search is required, like in combinatorial problems.
• Memoization or caching can be used to optimize the recursive calls, reducing redundant computations.

Recursion is generally not a good approach in scenarios where:

• The problem can be efficiently solved using simple iterative methods, without the overhead of function calls.
• The problem size can be too large, leading to excessive memory usage and potential stack overflow errors.
• The base case and termination condition are not well-defined, risking infinite loops or incorrect results.
• There is a risk of reaching the language’s recursion depth limit, especially for interpreted languages with limited call stack depth.

12. Explain with an example, the difference between direct and indirect recursion.

Direct recursion occurs when a function calls itself directly within its own body. Here’s an example of direct recursion to calculate the factorial of a number in C++:

#include <iostream>

int factorialDirect(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorialDirect(n - 1);
    }
}

int main() {
    int num = 5;
    int result = factorialDirect(num);
    std::cout << "Factorial of " << num << " is: " << result << std::endl;
    return 0;
}

Indirect recursion, on the other hand, involves multiple functions calling each other in a chain, eventually leading back to the initial function. Here’s an example of indirect recursion between function_A and function_B to print numbers in ascending and descending order alternately:

#include <iostream>

void function_B(int n); // Function declaration to resolve forward reference

void function_A(int n) {
    if (n > 0) {
        std::cout << n << " ";
        function_B(n - 1);
    }
}

void function_B(int n) {
    if (n > 0) {
        std::cout << n << " ";
        function_A(n - 1);
    }
}

int main() {
    int n = 5;
    function_A(n);
    return 0;
}

5 4 3 2 1 0 1 2 3 4 5

In the above example, function_A and function_B are calling each other alternatively, creating indirect recursion.

13. What is mutual recursion?

Mutual recursion occurs when two or more functions call each other in a cycle, forming a mutual relationship. Unlike indirect recursion, where the functions call each other alternately, mutual recursion creates a direct cycle of function calls.

Example (even and odd mutual recursion in C++):

#include <iostream>

bool is_odd(int n);

bool is_even(int n) {
    if (n == 0) {
        return true;
    } else {
        return is_odd(n - 1);
    }
}

bool is_odd(int n) {
    if (n == 0) {
        return false;
    } else {
        return is_even(n - 1);
    }
}

int main() {
    int number;

    std::cout << "Enter a number: ";
    std::cin >> number;

    if (is_even(number)) {
        std::cout << number << " is even." << std::endl;
    } else {
        std::cout << number << " is odd." << std::endl;
    }

    return 0;
}

Enter a number: 8
8 is even.

In the above example, is_even calls is_odd, and is_odd calls is_even, creating mutual recursion.

14. What is depth of recursive function calls? How is it related to memory usage?

The depth of recursive function calls refers to the number of times a function is called recursively before reaching the base case. Each time a function calls itself, a new stack frame is created to store its local variables and parameters. The depth of recursion determines how many stack frames will be present on the call stack at a given point in time.

The depth of recursive function calls is directly related to memory usage because each stack frame consumes memory. As the depth increases, more stack frames are created and stored in memory, which can lead to higher memory usage. If the depth becomes too large, it may exceed the available stack size and result in a stack overflow error.

15. What do you understand by the principle of recursion?

The principle of recursion revolves around the idea of solving complex problems by breaking them down into smaller, more manageable subproblems of the same type. The solution to the original problem is then obtained by combining the solutions of these smaller subproblems. Recursion follows the divide-and-conquer strategy, and it is guided by two main principles:

1. Base case: Every recursive algorithm must have a base case, which serves as the stopping condition for the recursive calls. When the base case is reached, the recursion stops, and a specific result is returned.
2. Recursive step: The algorithm must have a recursive step that reduces the original problem to a smaller subproblem. The algorithm continuously applies the same logic to the subproblem until the base case is met.

16. What are recursive data types and structures? Provide examples.

Recursive data types and structures refer to those where a data structure’s definition refers to instances of the same type within its own definition. In other words, the data structure can contain elements of the same type, leading to a self-referencing structure.

Examples of recursive data structures include:

1. Linked List: A linked list is a recursive data structure, where each node contains data and a reference to the next node in the list.
2. Binary Tree: A binary tree is a recursive data structure, where each node has at most two children, both of which are binary trees.
3. Tree: A general tree is a recursive data structure, where each node can have multiple children, each of which is also a tree.
4. Graph: A graph can be represented using recursive data structures, where vertices can be connected to other vertices, forming a recursive relationship.

17. What is the time and space complexity of recursive algorithms? How can it be optimized?

The time complexity of recursive algorithms depends on the number of recursive calls made and the work done at each level. If the recursion involves dividing the problem into two subproblems, like in binary search, the time complexity is often O(log n). In other cases, such as factorial or Fibonacci, where each recursive call results in multiple new recursive calls, the time complexity can be O(2^n) or O(n!) respectively.

The space complexity of recursive algorithms is determined by the maximum depth of recursion, which is equivalent to the maximum number of stack frames that can be present at the same time. The space complexity is typically O(n) for recursive algorithms, where n is the maximum recursion depth.

To optimize recursive algorithms, you can use techniques like:

• Tail recursion optimization, where the recursive call is the last operation in the function, enabling some languages and compilers to optimize the call stack and reuse stack frames.
• Memoization or dynamic programming, which involves caching the results of expensive function calls to avoid redundant computations and improve performance.

18. What is memoization? How does it improve the efficiency of recursive functions?

Memoization is a technique used to optimize recursive algorithms by caching the results of expensive function calls and reusing them when the same inputs occur again. It helps to avoid redundant computations and significantly improves the efficiency of recursive functions.

The basic idea behind memoization is to store the results of expensive function calls in a data structure (e.g., a dictionary) so that subsequent calls with the same inputs can retrieve the precomputed result instead of recalculating it. This technique is commonly used with dynamic programming to solve problems that have overlapping subproblems.

Example (Fibonacci with memoization in C++):

#include <iostream>
#include <unordered_map>

int fibonacciMemo(int n, std::unordered_map<int, int>& memo) {
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }

    if (n <= 2) {
        return 1;
    } else {
        int result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
        memo[n] = result;
        return result;
    }
}

int fibonacci(int n) {
    std::unordered_map<int, int> memo;
    return fibonacciMemo(n, memo);
}

int main() {
    int n = 10;
    int result = fibonacci(n);
    std::cout << "Fibonacci(" << n << ") = " << result << std::endl;
    return 0;
}

In the above example, the memo dictionary is used to store the results of Fibonacci calculations, avoiding redundant computations for the same inputs.

19. How does recursion work under the hood in programming languages?

Recursion works in programming languages through the call stack, which is a data structure used to manage function calls and local variables. When a function is called, its local variables and parameters are stored in a stack frame, and this frame is pushed onto the call stack. The function’s execution proceeds until it encounters a base case or a return statement.

In the case of recursion, when a function calls itself, a new stack frame is created and pushed onto the call stack, representing a new instance of the function with its own set of local variables and parameters. The recursive calls continue until the base case is reached, at which point the function starts returning values, and the recursion “unwinds” as each stack frame is popped off the call stack in reverse order.

If the recursion depth becomes too large or if the base case is not reached, the call stack can run out of memory, leading to a stack overflow error. This is why it is essential to have well-defined base cases and to optimize tail-recursive functions to prevent such errors.

20. What is a recursive descent parser? In what scenarios is it used?

A recursive descent parser is a top-down parsing technique used to analyze and process the syntax of a programming language or other formal language. It begins with the highest-level rule of the grammar and recursively descends into the grammar rules, using separate functions or procedures for each rule.

The parser builds a parse tree or abstract syntax tree (AST) for the input by matching the tokens sequentially and following the grammar rules defined by the language. It continues until the entire input is parsed, or it encounters an error indicating that the input does not conform to the grammar.

Recursive descent parsers are commonly used in compiler construction, interpreter design, and other language processing tasks because of their simplicity and ease of implementation. They are especially suitable for LL(k) grammars, where LL stands for “left-to-right, leftmost derivation,” and k indicates the number of lookahead symbols needed to determine the next grammar rule.

Coding Questions

1. Write a recursive function to calculate factorial of a number.

unsigned long long factorial(unsigned int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

2. Write a recursive program to calculate the Fibonacci series.

unsigned long long fibonacci(unsigned int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

3. Write a program to print all permutations of a string.

#include <iostream>
#include <string>
using namespace std;

void permute(string str, int left, int right) {
    if (left == right) {
        cout << str << endl;
    } else {
        for (int i = left; i <= right; i++) {
            swap(str[left], str[i]);
            permute(str, left + 1, right);
            swap(str[left], str[i]);
        }
    }
}

void printPermutations(string str) {
    permute(str, 0, str.length() - 1);
}

4. Implement a recursive solution to solve the Tower of Hanoi problem.

#include <iostream>
using namespace std;

void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    if (n == 1) {
        cout << "Move disk 1 from " << source << " to " << destination << endl;
        return;
    }
    towerOfHanoi(n - 1, source, destination, auxiliary);
    cout << "Move disk " << n << " from " << source << " to " << destination << endl;
    towerOfHanoi(n - 1, auxiliary, source, destination);
}

5. Write a recursive function to find the greatest common divisor of two numbers.

unsigned int gcd(unsigned int a, unsigned int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

6. Write a recursive program to implement binary search.

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& nums, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        return mid;
    } else if (nums[mid] > target) {
        return binarySearch(nums, target, left, mid - 1);
    } else {
        return binarySearch(nums, target, mid + 1, right);
    }
}

int search(vector<int>& nums, int target) {
    return binarySearch(nums, target, 0, nums.size() - 1);
}

7. Implement a recursive function to generate all subsets of a set.

#include <iostream>
#include <vector>
using namespace std;

void generateSubsets(vector<int>& nums, vector<int>& subset, int index) {
    if (index == nums.size()) {
        for (int num : subset) {
            cout << num << " ";
        }
        cout << endl;
        return;
    }
    subset.push_back(nums[index]);
    generateSubsets(nums,

 subset, index + 1);
    subset.pop_back();
    generateSubsets(nums, subset, index + 1);
}

void printSubsets(vector<int>& nums) {
    vector<int> subset;
    generateSubsets(nums, subset, 0);
}

8. Write a recursive program to reverse a string.

#include <iostream>
#include <string>
using namespace std;

void reverseString(string& str, int left, int right) {
    if (left >= right) {
        return;
    }
    swap(str[left], str[right]);
    reverseString(str, left + 1, right - 1);
}

void reverse(string& str) {
    reverseString(str, 0, str.length() - 1);
}

9. Write a recursive program to solve the N-Queens problem.

#include <iostream>
#include <vector>
using namespace std;

bool isSafe(vector<vector<bool>>& board, int row, int col, int n) {
    for (int i = 0; i < row; i++) {
        if (board[i][col]) {
            return false;
        }
    }
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j]) {
            return false;
        }
    }
    for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
        if (board[i][j]) {
            return false;
        }
    }
    return true;
}

bool solveNQueensUtil(vector<vector<bool>>& board, int row, int n) {
    if (row == n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << (board[i][j] ? "Q" : ".");
            }
            cout << endl;
        }
        return true;
    }
    bool result = false;
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col, n)) {
            board[row][col] = true;
            result = solveNQueensUtil(board, row + 1, n) || result;
            board[row][col] = false;
        }
    }
    return result;
}

void solveNQueens(int n) {
    vector<vector<bool>> board(n, vector<bool>(n, false));
    if (!solveNQueensUtil(board, 0, n)) {
        cout << "No solution exists." << endl;
    }
}

10. Write a recursive function to calculate the power of a number.

double power(double x, int n) {
    if (n == 0) {
        return 1.0;
    } else if (n > 0) {
        double result = power(x, n / 2);
        return (n % 2 == 0) ? result * result : result * result * x;
    } else {
        double result = power(x, -n / 2);
        return (n % 2 == 0) ? result * result : result * result / x;
    }
}

11. Implement a recursive solution to solve the problem of generating all balanced parentheses.

#include <iostream>
#include <vector>
using namespace std;

void generateParentheses(string current, int openCount, int closeCount, int n) {
    if (openCount == n && closeCount == n) {
        cout << current << endl;
        return;
    }
    if (openCount < n) {
        generateParentheses(current + "(", openCount + 1, closeCount, n);
    }
    if (closeCount < openCount) {
        generateParentheses(current + ")", openCount, closeCount + 1, n);
    }
}

void generateAllParentheses(int n) {
    generateParentheses("", 0, 0, n);
}

12. Write a recursive program to find all paths in a grid from top-left to bottom-right.

#include <iostream>
#include <vector>
using namespace std;

void findPaths(vector<vector<int>>& grid, int row, int col, string currentPath) {
    int m = grid.size();
    int n = grid[0].size();
    if (row == m - 1 && col == n - 1) {
        cout << currentPath << endl;
        return;
    }
    if (row < m - 1) {
        findPaths(grid, row + 1, col, currentPath + "D");
    }
    if (col < n - 1) {
        findPaths(grid, row, col + 1, currentPath + "R");
    }
}

void findAllPaths(vector<vector<int>>& grid) {
    findPaths(grid, 0, 0, "");
}

13. Implement a recursive function to solve the problem of coin change.

#include <iostream>
#include <vector>
using namespace std;

int coinChange(vector<int>& coins, int amount, int index) {
    if (amount == 0) {
        return 1;
    }
    if (amount < 0 || index >= coins.size()) {
        return 0;
    }
    int include = coinChange(coins, amount - coins[index], index);
    int exclude = coinChange(coins, amount, index + 1);
    return include + exclude;
}

int coinChangeCombinations(vector<int>& coins, int amount) {
    return coinChange(coins, amount, 0);
}

14. Write a recursive program to solve the Knapsack problem.

#include <iostream>
#include <vector>
using namespace std;

int knapsack(vector<int>& values, vector<int>& weights, int capacity, int index) {
    if (capacity == 0 || index >= values.size()) {
        return 0;
    }
    if (weights[index] > capacity) {
        return knapsack(values, weights, capacity, index + 1);
    }
    int include = values[index] + knapsack(values, weights, capacity - weights[index], index + 1);
    int exclude = knapsack(values, weights, capacity, index + 1);
    return max(include, exclude);
}

int solveKnapsack(vector<int>& values, vector<int>& weights, int capacity) {
    return knapsack(values, weights, capacity, 0);
}

15. Write a recursive program to solve the problem of generating all possible sorted arrays from alternate elements of two given sorted arrays.

#include <

iostream>
#include <vector>
using namespace std;

void generateSortedArrays(vector<int>& arr1, vector<int>& arr2, vector<int>& current, int i, int j, int m, int n, bool isOdd) {
    if (isOdd) {
        if (current.size() > 0) {
            for (int num : current) {
                cout << num << " ";
            }
            cout << endl;
        }
    } else {
        if (i == m && j == n) {
            for (int num : current) {
                cout << num << " ";
            }
            cout << endl;
            return;
        }
        if (i < m) {
            current.push_back(arr1[i]);
            generateSortedArrays(arr1, arr2, current, i + 1, j, m, n, !isOdd);
            current.pop_back();
        }
        if (j < n) {
            current.push_back(arr2[j]);
            generateSortedArrays(arr1, arr2, current, i, j + 1, m, n, !isOdd);
            current.pop_back();
        }
    }
}

void generateAllSortedArrays(vector<int>& arr1, vector<int>& arr2) {
    vector<int> current;
    int m = arr1.size();
    int n = arr2.size();
    generateSortedArrays(arr1, arr2, current, 0, 0, m, n, true);
}

16. Write a recursive function to find the length of a linked list.

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

int getLinkedListLength(Node* head) {
    if (head == nullptr) {
        return 0;
    }
    return 1 + getLinkedListLength(head->next);
}

17. Write a recursive program to solve the problem of tiling a floor with 2 x 1 and 2 x 2 tiles.

#include <iostream>
using namespace std;

int countWaysToTileFloor(int n) {
    if (n <= 2) {
        return n;
    }
    return countWaysToTileFloor(n - 1) + countWaysToTileFloor(n - 2);
}

18. Implement a recursive function to solve the problem of generating all permutations of a string.

#include <iostream>
#include <string>
using namespace std;

void generatePermutations(string str, int left, int right) {
    if (left == right) {
        cout << str << endl;
        return;
    }
    for (int i = left; i <= right; i++) {
        swap(str[left], str[i]);
        generatePermutations(str, left + 1, right);
        swap(str[left], str[i]);
    }
}

19. Write a recursive program to count the number of ways to climb a staircase with n steps, where you can climb either 1, 2, or 3 steps at a time.

#include <iostream>
using namespace std;

int countWaysToClimbStairs(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    }
    return countWaysToClimbStairs(n - 1) + countWaysToClimbStairs(n - 2) + countWaysToClimbStairs(n - 3);
}

20. Write a recursive function to find the depth/height of a binary tree.

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int findBinaryTreeHeight(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftHeight = findBinaryTreeHeight(root->left);
    int rightHeight = findBinaryTreeHeight(root->right);
    return 1 + max(leftHeight, rightHeight);
}

21. Write a recursive program to solve the problem of wildcard pattern matching.

#include <iostream>
#include <string>
using namespace std;

bool isMatch(string s, string p) {
    if (p.empty()) {
        return s.empty();
    }
    if (p[0] == '*') {
        if (s.empty()) {
            return isMatch(s, p.substr(1));
        } else {
            return isMatch(s.substr(1), p) || isMatch(s, p.substr(1));
        }
    } else if (!s.empty() && (p[0] == '?' || p[0] == s[

0])) {
        return isMatch(s.substr(1), p.substr(1));
    }
    return false;
}

22. Implement a recursive function to solve the problem of generating all the combinations of well-formed parentheses.

#include <iostream>
#include <vector>
using namespace std;

void generateParentheses(int n, int openCount, int closeCount, string current, vector<string>& result) {
    if (openCount == n && closeCount == n) {
        result.push_back(current);
        return;
    }
    if (openCount < n) {
        generateParentheses(n, openCount + 1, closeCount, current + "(", result);
    }
    if (closeCount < openCount) {
        generateParentheses(n, openCount, closeCount + 1, current + ")", result);
    }
}

23. Write a recursive program to solve the problem of validating a binary search tree.

#include <iostream>
#include <limits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isValidBSTHelper(TreeNode* root, long long minVal, long long maxVal) {
    if (root == nullptr) {
        return true;
    }
    if (root->val <= minVal || root->val >= maxVal) {
        return false;
    }
    return isValidBSTHelper(root->left, minVal, root->val) && isValidBSTHelper(root->right, root->val, maxVal);
}

bool isValidBST(TreeNode* root) {
    return isValidBSTHelper(root, LLONG_MIN, LLONG_MAX);
}

24. Write a recursive function to perform in-order, pre-order, and post-order traversal of a binary tree.

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inOrderTraversal(root->left);
    cout << root->val << " ";
    inOrderTraversal(root->right);
}

void preOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " ";
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

void postOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    cout << root->val << " ";
}

25. Write a recursive program to solve the problem of finding the minimum number of insertions to form a palindrome.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int minInsertionsForPalindrome(string str, int left, int right, vector<vector<int>>& dp) {
    if (left >= right) {
        return 0;
    }
    if (dp[left][right] != -1) {
        return dp[left][right];
    }
    if (str[left] == str[right]) {
        return dp[left][right] = minInsertionsForPalindrome(str, left + 1, right - 1, dp);
    } else {
        int insertLeft = minInsertionsForPalindrome(str, left + 1, right, dp);
        int insertRight = minInsert

ionsForPalindrome(str, left, right - 1, dp);
        return dp[left][right] = 1 + min(insertLeft, insertRight);
    }
}

26. Implement a recursive function to solve the problem of generating the power set of a given set.

#include <iostream>
#include <vector>
using namespace std;

void generatePowerSet(vector<int>& nums, int index, vector<int>& current, vector<vector<int>>& result) {
    result.push_back(current);
    for (int i = index; i < nums.size(); i++) {
        current.push_back(nums[i]);
        generatePowerSet(nums, i + 1, current, result);
        current.pop_back();
    }
}

27. Write a recursive program to solve the problem of generating all distinct binary strings of n bits.

#include <iostream>
#include <string>
using namespace std;

void generateBinaryStrings(int n, string current) {
    if (current.length() == n) {
        cout << current << endl;
        return;
    }
    generateBinaryStrings(n, current + '0');
    generateBinaryStrings(n, current + '1');
}

28. Implement a recursive function to solve the problem of partitioning a set into two subsets such that the difference of subset sums is minimum.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int minSubsetSumDifference(vector<int>& nums, int index, int sum1, int sum2) {
    if (index == nums.size()) {
        return abs(sum1 - sum2);
    }
    int diff1 = minSubsetSumDifference(nums, index + 1, sum1 + nums[index], sum2);
    int diff2 = minSubsetSumDifference(nums, index + 1, sum1, sum2 + nums[index]);
    return min(diff1, diff2);
}

29. Write a recursive program to solve the problem of finding the longest increasing subsequence.

#include <iostream>
#include <vector>
using namespace std;

int findLongestIncreasingSubsequence(vector<int>& nums, int index, int prev) {
    if (index == nums.size()) {
        return 0;
    }
    int include = 0;
    if (nums[index] > prev) {
        include = 1 + findLongestIncreasingSubsequence(nums, index + 1, nums[index]);
    }
    int exclude = findLongestIncreasingSubsequence(nums, index + 1, prev);
    return max(include, exclude);
}

30. Write a recursive function to solve the problem of finding the longest common subsequence.

#include <iostream>
#include <vector>
using namespace std;

int findLongestCommonSubsequence(string text1, string text2, int m, int n, vector<vector<int>>& dp) {
    if (m == 0 || n == 0) {
        return 0;
    }
    if (dp[m][n] != -1) {
        return dp[m][n];
    }
    if (text1[m - 1] == text2[n - 1]) {
        return dp[m][n] = 1 + findLongestCommonSubsequence(text1, text2, m - 1, n - 1, dp);
    } else {
        return dp[m][n] = max(findLongestCommonSubsequence(text1, text2, m - 1, n, dp), findLongestCommonSubsequence(text1, text2, m,

 n - 1, dp));
    }
}

MCQ Questions

1. What is recursion?

a) A programming language
b) A data structure
c) A mathematical technique
d) A control flow mechanism

Answer: d) A control flow mechanism

2. In recursion, a function calls itself __________.

a) Once
b) Twice
c) Multiple times
d) Never

Answer: c) Multiple times

3. What is the base case in a recursive function?

a) The initial condition
b) The final condition
c) The stopping condition
d) The recursive condition

Answer: c) The stopping condition

4. What is the purpose of a base case in recursion?

a) To stop the recursion
b) To initialize the recursion
c) To modify the recursion
d) To optimize the recursion

Answer: a) To stop the recursion

5. What is the difference between direct recursion and indirect recursion?

a) Direct recursion involves a single function calling itself, while indirect recursion involves multiple functions calling each other.
b) Direct recursion is faster than indirect recursion.
c) Direct recursion requires more memory than indirect recursion.
d) Direct recursion and indirect recursion are the same.

Answer: a) Direct recursion involves a single function calling itself, while indirect recursion involves multiple functions calling each other.

6. Which data structure is commonly used in recursion?

a) Stack
b) Queue
c) Array
d) Linked list

Answer: a) Stack

7. What is the time complexity of a recursive function with a single recursive call?

a) O(1)
b) O(log n)
c) O(n)
d) O(n^2)

Answer: b) O(log n)

8. What is the purpose of a recursive function?

a) To simplify the code
b) To improve performance
c) To solve complex problems by breaking them into smaller, simpler subproblems
d) To reduce memory usage

Answer: c) To solve complex problems by breaking them into smaller, simpler subproblems

9. Which of the following problems can be solved using recursion?

a) Sorting a list
b) Finding the maximum element in an array
c) Calculating the factorial of a number
d) Reversing a string

Answer: c) Calculating the factorial of a number

10. What is tail recursion?

a) When a function calls itself as the last operation before returning
b) When a function calls itself at the beginning of its execution
c) When a function calls itself multiple times within a loop
d) When a function calls another function recursively

Answer: a) When a function calls itself as the last operation before returning

11. Which of the following statements is true about recursion?

a) Recursion is always more efficient than iteration.
b) Recursion is always easier to implement than iteration.
c) Recursion can lead to infinite loops if not implemented correctly.
d) Recursion can only be used with certain programming languages.

Answer: c) Recursion can lead to infinite loops if not implemented correctly.

12. What is the base case in a recursive function?

a) The initial condition
b) The final condition
c) The stopping condition
d) The recursive condition

Answer: c) The stopping condition

13. What is the difference between recursion and iteration?

a) Recursion is a control flow mechanism, while iteration is a loop.

b) Recursion is slower than iteration.
c) Recursion uses less memory than iteration.
d) Recursion and iteration are the same.

Answer: a) Recursion is a control flow mechanism, while iteration is a loop.

14. What is the maximum number of recursive calls that can be made in a recursive function?

a) One
b) Two
c) Three
d) There is no limit

Answer: d) There is no limit

15. Which of the following is NOT a required component of a recursive function?

a) Base case
b) Recursive case
c) Termination condition
d) Function arguments

Answer: c) Termination condition

16. In recursion, what is the role of the call stack?

a) It stores the return addresses of recursive function calls.
b) It stores the values of local variables for each recursive call.
c) It controls the order in which recursive calls are executed.
d) It is not used in recursion.

Answer: a) It stores the return addresses of recursive function calls.

17. What is the output of a recursive function?

a) Return value
b) Side effects
c) Both return value and side effects
d) None of the above

Answer: c) Both return value and side effects

18. Which of the following is an example of a recursive algorithm?

a) Bubble sort
b) Binary search
c) Linear search
d) Insertion sort

Answer: b) Binary search

19. Which of the following is a disadvantage of using recursion?

a) It requires less memory than iteration.
b) It is more difficult to understand and debug.
c) It always leads to better performance than iteration.
d) It can only be used for simple problems.

Answer: b) It is more difficult to understand and debug.

20. What is the difference between tail recursion and head recursion?

a) Tail recursion is faster than head recursion.
b) Tail recursion is a type of recursion, while head recursion is not.
c) Tail recursion involves a function calling itself at the end, while head recursion involves a function calling itself at the beginning.
d) Tail recursion and head recursion are the same.

Answer: c) Tail recursion involves a function calling itself at the end, while head recursion involves a function calling itself at the beginning.

21. Which of the following is an example of a recursive data structure?

a) Array
b) Queue
c) Stack
d) Linked list

Answer: d) Linked list

22. What is the space complexity of a recursive algorithm?

a) O(1)
b) O(n)
c) O(log n)
d) O(n!)

Answer: c) O(log n)

23. What is the difference between direct and indirect recursion?

a) Direct recursion involves a function calling itself, while indirect recursion involves multiple functions calling each other.
b) Direct recursion is more efficient than indirect recursion.
c) Direct recursion uses less memory than indirect recursion.
d) Direct recursion and indirect recursion are the same.

Answer: a) Direct recursion involves a function calling itself, while indirect recursion involves multiple functions calling each other.

24. Which of the following is a limitation of recursion?

a) It can only be used for small-sized problems.
b) It always requires additional memory.
c) It can lead to stack overflow if the recursion depth is too high.
d) It is slower than iteration.

Answer: c) It can lead to stack overflow if the recursion depth is too high.

25. In recursion, what is the role of the base case?

a) To stop the recursion
b) To initialize the recursion
c) To modify the recursion
d) To optimize the recursion

Answer: a) To stop the recursion

26. Which of the following is NOT required for a recursive function?

a) Base case
b) Recursive call
c) Looping mechanism
d) Function arguments

Answer: c) Looping mechanism

27. What is the relationship between recursion and problem-solving by dividing and conquering?

a) Recursion is a technique used in problem-solving by dividing and conquering.
b) Recursion and problem-solving by dividing and conquering are unrelated concepts.
c) Recursion is a more efficient approach than problem-solving by dividing and conquering.
d) Problem-solving by dividing and conquering is a more efficient approach than recursion.

Answer: a) Recursion is a technique used in problem-solving by dividing and conquering.

28. What happens if a recursive function does not have a base case?

a) The function will run indefinitely.
b) The function will return an error.
c) The function will terminate immediately.
d) The function will run with no output.

Answer: a) The function will run indefinitely.

29. Which data structure is commonly used to implement recursion in programming languages?

a) Queue
b) Stack
c) Linked list
d) Heap

Answer: b) Stack

30. In recursion, what is the concept of “divide and conquer”?

a) Breaking down a problem into smaller subproblems
b) Combining the results of smaller subproblems to solve the main problem
c) Repeating the process of dividing and conquering until the problem is solved
d) All of the above

Answer: d) All of the above