Recursion Practice Problems with Solutions

Google Translate Icon

Here’s what Google has to say on recursion – Did you mean: recursion

Recursion

Strange, isn’t? Or not!!

 
Recursion is a problem-solving technique that involves breaking a problem into smaller instances of the same problem (also called subproblems) until we get a small enough subproblem having a trivial solution. We can say that recursion is “defining a problem in terms of itself” as it involves a function calling itself with a base case to terminate the infinite loop.

Recursion is an important concept in computer science and a very powerful tool in writing algorithms. It allows us to write very elegant solutions to problems that may otherwise be very difficult to implement iteratively. It might be a little confusing and difficult to understand, especially for beginners but once you understand it, a whole new world of programming will open for you. Recursion just takes practice to get good at and nothing is more interesting than finding a solution to a problem the recursive way.

Backtracking:

  1. Find all combinations of elements satisfying given constraintsMedium
  2. K–Partition Problem | Printing all partitionsHard
  3. Find all distinct combinations of a given length with repetition allowedMedium
  4. Print all combinations of numbers from 1 to n having sum nMedium
  5. Print all possible solutions to N–Queens problemHard
  6. Print all possible Knight’s tours on a chessboardHard
  7. Find the shortest path in a mazeMedium
  8. Find the longest possible route in a matrixMedium
  9. Find the path from source to destination in a matrix that satisfies given constraintsMedium
  10. Find the total number of unique paths in a maze from source to destinationMedium
  11. Magnet PuzzleHard
  12. Find all paths from the first cell to the last cell of a matrixMedium
  13. Print all shortest routes in a rectangular gridMedium
  14. Find all occurrences of the given string in a character matrixHard
  15. Generate a list of possible words from a character matrixHard
  16. Find all permutations of a string – C++, Java, PythonHard
  17. Print all distinct subsets of a given setHard

String:

  1. Check if a string is a rotated palindrome or notMedium
  2. Check if a repeated subsequence is present in a string or notHard
  3. Find all interleaving of given stringsEasy
  4. Find all possible combinations of words formed from the mobile keypadHard
  5. Find all possible combinations by replacing given digits with characters of the corresponding listHard
  6. Find all strings of a given length containing balanced parenthesesMedium
  7. Find all combinations of non-overlapping substrings of a stringMedium
  8. Determine whether a string is a palindrome or notEasy
  9. Print all combinations of phrases formed by picking words from each of the given listsMedium
  10. Break a string into all possible combinations of non-overlapping substringsMedium
  11. Remove adjacent duplicate characters from a stringEasy
  12. Find all n-digit strictly increasing numbers (Bottom-up and Top-down approach)Medium
  13. Find all n-digit binary numbers having more 1’s than 0’s for any prefixMedium
  14. Find all n-digit numbers with a given sum of digitsHard
  15. Find all n-digit binary numbers with an equal sum of bits in their two halvesHard
  16. Find all n-digit numbers with equal sum of digits at even and odd indicesHard
  17. Find all lexicographic permutations of a stringHard
  18. Reverse a string using recursionEasy
  19. Number to word conversionHard
  20. Implement strstr function in JavaEasy
  21. Find the minimum number possible by doing at-most k swapsMedium
  22. Determine whether a string matches with a given patternHard

Array:

  1. Replace every array element with the product of every other elementMedium
  2. Find all distinct combinations of a given length – IMedium
  3. Find all distinct combinations of a given length – IIMedium
  4. Find a triplet with the given sum in an arrayMedium
  5. Reverse every consecutive m-elements of a subarrayMedium
  6. Maximum Product Subset ProblemEasy
  7. 4–Sum Problem | Quadruplets with a given sumMedium
  8. Quickselect AlgorithmMedium
  9. Add elements of two arrays into a new arrayEasy
  10. Print all combinations of positive integers in increasing order that sums to a given numberHard
  11. 3–partition problem extended | Printing all partitionsHard
  12. Check if an array represents a min-heap or notMedium
  13. Convert max heap to min heap in linear timeEasy
  14. Find the odd occurring element in an array in logarithmic timeMedium
  15. Generate the power set of a given setMedium

Matrix:

  1. Print matrix in spiral orderMedium
  2. Replace all occurrences of 0 that are not surrounded by 1 in a binary matrixMedium
  3. Young Tableau | Insert, Search, Extract-Min, Delete, ReplaceHard
  4. Replace all occurrences of 0 that are surrounded by 1 in a binary matrixMedium
  5. Sort an array using Young tableauHard
  6. Flood Fill AlgorithmMedium
  7. Find the shortest path from source to destination in a matrix that satisfies given constraintsHard
  8. Find minimum passes required to convert all negative values in a matrixHard

Divide & Conquer:

  1. Binary Search AlgorithmEasy
  2. Find the number of rotations in a circularly sorted arrayEasy
  3. Find the smallest missing element from a sorted arrayMedium
  4. Find the number of 1’s in a sorted binary arrayEasy
  5. Find the peak element in an arrayMedium
  6. Maximum Subarray Sum using Divide and ConquerMedium
  7. Find floor and ceil of a number in a sorted array (Recursive solution)Easy
  8. Find the frequency of each element in a sorted array containing duplicatesEasy
  9. Find the minimum and maximum element in an array using Divide and ConquerEasy
  10. Longest Common Prefix (LCP) ProblemEasy
  11. Exponential searchEasy
  12. Unbounded Binary SearchEasy
  13. Efficiently implement power functionEasy

Linked List:

  1. Clone a Linked ListEasy
  2. Delete a linked listEasy
  3. Split a linked list into two lists where each list contains alternating elements from itMedium
  4. Construct a linked list by merging alternate nodes of two given listsEasy
  5. Merge two sorted linked lists into oneMedium
  6. Efficiently merge k sorted linked listsHard
  7. Reverse a Linked List – Recursive SolutionHard
  8. Reverse every group of k nodes in a linked listMedium
  9. Find k’th node from the end of a linked listEasy
  10. Merge alternate nodes of two linked lists into the first listMedium
  11. Delete every N nodes in a linked list after skipping M nodesEasy
  12. Rearrange linked list in a specific manner in linear timeMedium
  13. Check if a linked list is palindrome or notMedium
  14. Move the last node to the front of a linked listEasy
  15. Rearrange a linked list by separating odd nodes from even onesMedium
  16. Recursively check if the linked list of characters is palindrome or notMedium
  17. Add a single-digit number to a linked list representing a numberMedium
  18. Reverse every alternate group of k nodes in a linked listMedium
  19. Determine whether a linked list is palindrome or notMedium
  20. Reverse a doubly linked listEasy
  21. Pairwise swap adjacent nodes of a linked listMedium
  22. Flatten a Linked ListHard
  23. Check if a linked list of strings is palindromicEasy
  24. Flatten a multilevel linked listMedium
  25. Clone a linked list with random pointerHard
  26. Update random pointer for each linked list node to point to the maximum nodeMedium

Sorting:

  1. Insertion Sort AlgorithmEasy
  2. Selection Sort AlgorithmEasy
  3. Bubble Sort AlgorithmEasy
  4. Merge Sort AlgorithmEasy
  5. Quicksort AlgorithmMedium
  6. Hybrid QuickSort AlgorithmMedium
  7. Quicksort using Dutch National Flag AlgorithmMedium
  8. Quicksort algorithm using Hoare’s partitioning schemeMedium
  9. Heap Sort AlgorithmMedium
  10. Introsort Algorithm – Overview and C++ ImplementationHard
  11. Merge sort algorithm for a singly linked listHard
  12. Sort a doubly-linked list using merge sortMedium
  13. Inversion count of an arrayHard
  14. Find surpasser count for each array elementHard
  15. Water Jugs ProblemHard

Binary Tree:

  1. Inorder Tree TraversalMedium
  2. Preorder Tree TraversalMedium
  3. Postorder Tree TraversalMedium
  4. Check if two binary trees are identical or notEasy
  5. Print bottom view of a binary treeMedium
  6. Print top view of a binary treeMedium
  7. In-place convert a binary tree to its sum treeEasy
  8. Determine whether the given binary tree nodes are cousins of each otherMedium
  9. Print cousins of a given node in a binary treeMedium
  10. Check if a binary tree is a sum tree or notMedium
  11. Combinations of words formed by replacing given numbers with corresponding alphabetsHard
  12. Determine whether a binary tree is a subtree of another binary treeMedium
  13. Find the diameter of a binary treeMedium
  14. Check if a binary tree is symmetric or notEasy
  15. Convert a binary tree to its mirrorEasy
  16. Determine if a binary tree can be converted to another by doing any number of swaps of childrenEasy
  17. Find the Lowest Common Ancestor (LCA) of two nodes in a binary treeMedium
  18. Print all paths from the root to leaf nodes of a binary treeEasy
  19. Find ancestors of a given node in a binary treeMedium
  20. Find distance between given pairs of nodes in a binary treeHard
  21. Find the diagonal sum of a binary treeMedium
  22. Sink nodes containing zero to the bottom of a binary treeHard
  23. Convert a binary tree to a full tree by removing half nodesMedium
  24. Truncate a binary tree to remove nodes that lie on a path having a sum less than kMedium
  25. Find maximum sum root to leaf path in a binary treeMedium
  26. Check if a binary tree is height-balanced or notMedium
  27. Convert binary tree to Left-child right-sibling binary treeMedium
  28. Print all paths from leaf to root node of a binary treeMedium
  29. Find all nodes at a given distance from leaf nodes in a binary treeHard
  30. Count all subtrees having the same value of nodes in a binary treeMedium
  31. Find the maximum difference between a node and its descendants in a binary treeMedium
  32. Find the maximum sum path between two leaves in a binary treeHard
  33. Construct a binary tree from inorder and preorder traversalHard
  34. Construct a binary tree from inorder and postorder traversalsHard
  35. Construct a binary tree from inorder and level order sequenceHard
  36. Construct a full binary tree from the preorder sequence with leaf node informationHard
  37. Construct a full binary tree from a preorder and postorder sequenceHard
  38. Find postorder traversal of a binary tree from its inorder and preorder sequenceMedium
  39. Set next pointer to the inorder successor of all nodes in a binary treeEasy
  40. Find preorder traversal of a binary tree from its inorder and postorder sequenceHard
  41. Find difference between sum of all nodes present at odd and even levels in a binary treeEasy
  42. Clone a binary tree with random pointersHard
  43. Threaded Binary Tree – Overview and ImplementationMedium
  44. Determine if a binary tree satisfies the height-balanced property of a red–black treeMedium
  45. Construct an ancestor matrix from a binary treeEasy
  46. Find all possible binary trees having the same inorder traversalHard
  47. Perform boundary traversal on a binary treeMedium
  48. Check if each node of a binary tree has exactly one childEasy
  49. Evaluate a Binary Expression TreeEasy
  50. Construction of an expression treeEasy
  51. Fix children-sum property in a binary treeMedium
  52. Maximum path sum in a binary treeHard
  53. Create a mirror of an m–ary treeEasy
  54. Print a two-dimensional view of a binary treeEasy
  55. Construct a Cartesian tree from an inorder traversalMedium
  56. Calculate the height of a binary tree with leaf nodes forming a circular doubly linked listMedium
  57. Link nodes present in each level of a binary tree in the form of a linked listHard
  58. Convert a ternary tree to a doubly-linked listMedium
  59. Extract leaves of a binary tree into a doubly-linked listMedium
  60. Find the vertical sum of a binary treeHard
  61. In-place convert a binary tree to a doubly-linked listHard
  62. Check whether the leaf traversal of given binary trees is the same or notHard
  63. Efficiently print all nodes between two given levels in a binary treeEasy
  64. Calculate the height of a binary treeEasy
  65. Delete a binary treeEasy
  66. Level order traversal of a binary treeEasy
  67. Spiral order traversal of a binary treeMedium
  68. Reverse level order traversal of a binary treeEasy
  69. Print left view of a binary treeEasy
  70. Find the next node at the same level as the given node in a binary treeMedium
  71. Check if a binary tree is a complete binary tree or notMedium
  72. Print diagonal traversal of a binary treeMedium
  73. Invert Binary TreeEasy
  74. Convert a binary tree into a doubly-linked list in spiral orderHard
  75. Check if a binary tree is a min-heap or notMedium
  76. Invert alternate levels of a perfect binary treeHard
  77. Perform vertical traversal of a binary treeMedium
  78. Compute the maximum number of nodes at any level in a binary treeEasy
  79. Print right view of a binary treeMedium
  80. Find the minimum depth of a binary treeEasy
  81. Print nodes of a binary tree in vertical orderMedium

Binary Search Tree:

  1. Insertion in a BSTEasy
  2. Search a given key in BSTEasy
  3. Deletion from BST (Binary Search Tree)Medium
  4. Construct a balanced BST from the given keysEasy
  5. Determine whether a given binary tree is a BST or notMedium
  6. Check if the given keys represent the same BSTs or not without building BSTHard
  7. Find inorder predecessor for the given key in a BSTMedium
  8. Find the Lowest Common Ancestor (LCA) of two nodes in a BSTEasy
  9. Find k’th smallest and k’th largest element in a BSTEasy
  10. Find floor and ceil in a Binary Search TreeMedium
  11. Convert a binary tree to BST by maintaining its original structureMedium
  12. Remove nodes from a BST that have keys outside a valid rangeMedium
  13. Find a pair with the given sum in a BSTEasy
  14. Find k’th smallest node in a Binary Search Tree (BST)Easy
  15. Find inorder successor for the given key in a BSTMedium
  16. Fix a binary tree that is only one swap away from becoming a BSTHard
  17. Update every key in a BST to contain the sum of all greater keysMedium
  18. Check if a given sequence represents the preorder traversal of a BSTHard
  19. Build a Binary Search Tree from a postorder sequenceHard
  20. Build a Binary Search Tree from a preorder sequenceHard
  21. Count subtrees in a BST whose nodes lie within a given rangeMedium
  22. Find the size of the largest BST in a binary treeHard
  23. Print complete Binary Search Tree (BST) in increasing orderEasy
  24. Print binary tree structure with its contents in C++Medium
  25. Treap Data StructureBeginner
  26. Implementation of Treap Data Structure (Insert, Search, and Delete)Hard
  27. Merge two BSTs into a doubly-linked list in sorted orderHard
  28. Construct a height-balanced BST from an unbalanced BSTHard
  29. Construct a height-balanced BST from a sorted doubly linked listHard
  30. Find a triplet with the given sum in a BSTHard
  31. Convert a Binary Search Tree into a Min HeapHard

Dynamic Programming:

  1. Longest Common Subsequence ProblemMedium
  2. Longest Common Subsequence of k–sequencesMedium
  3. Longest Common Subsequence | Finding all LCSHard
  4. Longest Palindromic Subsequence using Dynamic ProgrammingMedium
  5. Longest Repeated Subsequence ProblemMedium
  6. Implement Diff UtilityMedium
  7. Shortest Common Supersequence ProblemMedium
  8. Shortest Common Supersequence | Finding all SCSHard
  9. Shortest Common Supersequence Problem using LCSHard
  10. Longest Increasing Subsequence using Dynamic ProgrammingHard
  11. Longest Decreasing Subsequence ProblemHard
  12. Maximum Sum Increasing Subsequence ProblemMedium
  13. The Levenshtein distance (Edit distance) ProblemMedium
  14. Find the size of the largest square submatrix of 1’s present in a binary matrixMedium
  15. Matrix Chain Multiplication using Dynamic ProgrammingHard
  16. Find minimum cost to reach the last cell of a matrix from its first cellMedium
  17. Find the longest sequence formed by adjacent numbers in the matrixMedium
  18. Count the number of paths in a matrix with a given cost to reach the destination cellMedium
  19. 0–1 Knapsack ProblemMedium
  20. Partition Problem using Dynamic ProgrammingMedium
  21. Subset Sum Problem – Dynamic Programming SolutionMedium
  22. 3–Partition ProblemMedium
  23. Minimum Sum Partition ProblemHard
  24. Rod Cutting ProblemMedium
  25. Maximum Product Rod CuttingMedium
  26. Coin change-making problemMedium
  27. Coin Change ProblemHard
  28. Total possible solutions to a linear equation of k variablesHard
  29. Longest Alternating Subsequence ProblemMedium
  30. Count the number of times a pattern appears in a given string as a subsequenceHard
  31. Collect maximum points in a matrix by satisfying given constraintsHard
  32. Find all N-digit binary strings without any consecutive 1’sEasy
  33. Count total possible combinations of n-digit numbers in a mobile keypadMedium
  34. Word Break Problem – Dynamic ProgrammingHard
  35. Check if a string is k–palindrome or notHard
  36. Find total ways to achieve a given sum with n throws of dice having k facesMedium
  37. Wildcard Pattern MatchingHard
  38. Find the number of ways to fill an N × 4 matrix with 1 × 4 tilesMedium
  39. Ways to reach the bottom-right corner of a matrix with exactly k turns allowedHard
  40. Weighted Interval Scheduling ProblemMedium
  41. Find total ways to reach n’th stair with at-most m stepsMedium
  42. Find total ways to reach the n’th stair from the bottomMedium
  43. Find the minimum number of deletions required to convert a string into a palindromeMedium
  44. Pots of Gold Game Problem using Dynamic ProgrammingHard
  45. Find minimum cuts needed for the palindromic partition of a stringHard
  46. Find minimum jumps required to reach the destinationMedium
  47. Find the probability that a person is alive after taking n steps on an islandMedium
  48. Longest Increasing Subsequence using LCSMedium
  49. Count all paths in a matrix from the first cell to the last cellEasy
  50. Check if a string matches with the given wildcard patternHard
  51. Check if a string is interleaving of two other given stringsMedium
  52. Find all employees who directly or indirectly reports to a managerHard
  53. Find optimal cost to construct a binary search treeHard
  54. Find the maximum sum of a subsequence with no adjacent elementsMedium
  55. Minimum-weight triangulation of a convex polygonHard
  56. Find maximum profit that can be earned by conditionally selling stocksEasy
  57. Program to find n’th Fibonacci numberEasy
  58. Count decodings of a given sequence of digitsMedium
  59. Hat Check Problem – Counting DerangementsMedium
  60. Maximum Independent Set ProblemMedium
  61. Find the minimum number of squares that sum to a given numberMedium
  62. Truncate an integer array such that 2×min becomes more than maxHard
  63. Find ways to calculate a target from elements of the specified arrayMedium
  64. Find the length of the longest path in a matrix with consecutive charactersMedium
  65. Collect maximum value of coins in a matrixHard
  66. Single-Source Shortest Paths – Bellman–Ford AlgorithmMedium
  67. All-Pairs Shortest Paths – Floyd Warshall AlgorithmEasy

Programming Puzzles:

  1. Implement power function without using multiplication and division operatorsEasy
  2. Print all numbers between 1 to N without using a semicolonMedium
  3. Determine the if condition to print the specific outputEasy
  4. Tower of Hanoi ProblemMedium
  5. Print all numbers between 1 to N without using any loop | 4 methodsEasy
  6. Multiply two numbers without using a multiplication operator or loopsEasy
  7. Find minimum number without using conditional statement or ternary operatorMedium
  8. Perform division of two numbers without using division operatorMedium
  9. Find maximum number without using conditional statement or ternary operatorEasy

Graphs:

  1. Depth First Search (DFS)Medium
  2. Breadth-First Search (BFS)Medium
  3. Arrival and departure time of vertices in DFSEasy
  4. Determine whether a graph is Bipartite using DFSMedium
  5. Topological Sort Algorithm for DAGMedium
  6. Transitive closure of a graphEasy
  7. Determine whether an undirected graph is a tree (Acyclic Connected Graph)Medium
  8. 2–Edge Connectivity in a graphHard
  9. Check if a digraph is a DAG (Directed Acyclic Graph) or notMedium
  10. Disjoint–Set Data Structure (Union–Find Algorithm)Medium
  11. Check if a graph is strongly connected or notEasy
  12. Check if a graph is strongly connected or not using one DFS TraversalHard
  13. Union–Find Algorithm for cycle detection in a graphMedium
  14. Find the cost of the shortest path in DAG using one pass of Bellman–FordMedium
  15. Find all Possible Topological Orderings of a DAGHard
  16. Find correct order of alphabets in a given dictionary of ancient originHard
  17. Find the longest path in a Directed Acyclic Graph (DAG)Hard
  18. Print all k–colorable configurations of a graph (Vertex coloring of a graph)Medium
  19. Print all Hamiltonian paths present in a graphHard
  20. Kruskal’s Algorithm for finding Minimum Spanning TreeHard
  21. Eulerian cycle in directed graphsHard
  22. Find root vertex of a graphMedium
  23. Check whether an undirected graph is EulerianMedium
  24. Check if a set of words can be rearranged to form a circleHard
  25. Find itinerary from the given list of departure and arrival airportsEasy
  26. Check if an undirected graph contains a cycle or notMedium
  27. Compute the least cost path in a weighted digraph using BFSMedium
  28. Find the path between given vertices in a directed graphEasy

Stack:

  1. Recursive solution to sort a stackHard
  2. Reverse a stack using recursionHard
  3. Reverse a string using a stack data structureEasy
  4. Reverse an array in C++Easy
  5. Find all binary strings that can be formed from a wildcard patternMedium
  6. Implement a stack using the queue data structureMedium
  7. Implement a queue using the stack data structureMedium

Trie:

  1. Lexicographic sorting of a given set of keysMedium
  2. Find the maximum occurring word in a given set of stringsEasy
  3. Find first k maximum occurring words in a given set of stringsMedium
  4. Word Break Problem – Using Trie Data StructureMedium
  5. Find all words matching a pattern in the given dictionaryMedium
  6. Find the shortest unique prefix for every word in an arrayMedium

Rate this post

Average rating 4.78/5. Vote count: 137

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Tell us how we can improve this post?




Thanks for reading.

Please use our online compiler to post code in comments using C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.

Like us? Refer us to your friends and help us grow. Happy coding :)



Subscribe
Notify of
guest
4 Comments
Most Voted
Newest Oldest
Inline Feedbacks
View all comments
Do NOT follow this link or you will be banned from the site!