Recursion Practice Problems with Solutions

 
Recursion is a problem solving technique which involves breaking a problem into smaller instances of the same problem (also called as subproblems) until we get small enough subproblem that has 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 important concept in computer science and 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 little confusing and difficult to understand, especially for the 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 –

 

Strings –

  • Reverse a string using recursion
  • Find all binary strings that can be formed from given wildcard pattern
  • Find all interleavings of given strings
  • Find all possible combinations of words formed from mobile keypad
  • Find all combinations by replacing given digits with characters of the corresponding list
  • Find all Permutations of a given string
  • Find all strings of given length containing balanced parentheses
  • Find all N-digit binary numbers having more 1’s than 0’s for any prefix
  • Find all N-digit numbers with given sum of digits
  • Find all Lexicographic Permutations of a String
  • Find all N-digit binary numbers with equal sum of bits in its two halves
  • Generate all Permutations of a String in Java | Recursive & Iterative
  • Reverse given string using Recursion
  • Reverse a String in Java in 10 different ways
  • Determine if a given string is palindrome or not
  •  

    Array –

  • Replace each element of array with product of every other element without using / operator
  • Find all distinct combinations of given length
  • Find all distinct combinations of given length with repetition allowed
  • Find maximum sum of subsequence with no adjacent elements
  • All combinations of elements satisfying given constraints
  • Find all N-digit strictly increasing numbers (Bottom-Up and Top-Down Approach)
  • Count total possible combinations of N-digit numbers in a mobile keypad
  • Find Triplet with given sum in an array
  • Find all N-digit numbers with given sum of digits
  • 4 sum problem | Quadruplets with given sum
  • Maximum Product Subset Problem
  • Quickselect Algorithm
  • Longest Decreasing Subsequence Problem
  • 4 sum problem | Quadruplets with given sum
  • Print all distinct Subsets of a given Set
  • 3-partition problem extended | Print all partitions
  •  

    Matrix –

     

    Divide & Conquer –

     

    Linked List –

     

    Graphs –

     

    Sorting –

     

    Heap –

     

    Binary Tree –

  • Check if two binary trees are identical or not | Iterative & Recursive
  • Calculate height of binary tree | Iterative & Recursive
  • Delete given Binary Tree | Iterative & Recursive
  • Level Order Traversal of Binary Tree
  • Spiral Order Traversal of Binary Tree
  • Reverse Level Order Traversal of Binary Tree
  • Print left view of binary tree
  • Print Bottom View of Binary Tree
  • Print Top View of Binary Tree
  • Find next node in same level for given node in a binary tree
  • Check if given binary tree is complete binary tree or not
  • Determine if given two nodes are cousins of each other
  • Print cousins of given node in a binary tree
  • In-place convert given binary tree to its sum tree
  • Check if given binary tree is a sum tree or not
  • Combinations of words formed by replacing given numbers with corresponding alphabets
  • Determine if given binary tree is a subtree of another binary tree or not
  • Find diameter of a binary tree
  • Check if given binary Tree is symmetric or not
  • Convert binary tree to its mirror
  • Check if tree can be converted to another by doing any no. of swaps of left & right child
  • Postorder Tree Traversal | Iterative & Recursive
  • Preorder Tree Traversal | Iterative & Recursive
  • Inorder Tree Traversal | Iterative & Recursive
  • Find Lowest Common Ancestor (LCA) of two nodes in a binary tree
  • Print all paths from root to leaf nodes in given binary tree
  • Find ancestors of given node in a Binary Tree
  • Find the distance between given pairs of nodes in a binary tree
  • Find Vertical Sum in a given Binary Tree
  • Print nodes in vertical order of a given Binary Tree (Vertical Traversal)
  • Find the diagonal sum of given binary tree
  • Print Diagonal Traversal of Binary Tree
  • In-place convert convert given Binary Tree to Doubly Linked List
  • Sink nodes containing zero to the bottom of the binary tree
  • Convert given binary tree to full tree by removing half nodes
  • Truncate given binary tree to remove nodes which lie on a path having sum less than K
  • Find maximum sum root to leaf path in a binary tree
  • Check if given binary tree is height balanced or not
  • Convert normal binary tree to Left-child right-sibling binary tree
  • Trie Implementation | Insert, Search and Delete
  • Invert given Binary Tree | Recursive and Iterative solution
  • Print Right View of a Binary Tree
  • Find maximum width of given binary tree
  • C++ Program to Print Binary Tree Structure
  •  

    Binary Search Tree –

     

    Dynamic Programming –

  • Longest Common Subsequence | Introduction & LCS Length
  • Longest Common Subsequence | Finding all LCS
  • Longest Common Subsequence of K-sequences
  • Longest Palindromic Subsequence using Dynamic Programming
  • Longest Repeated Subsequence problem
  • Shortest Common Supersequence | Introduction & SCS Length
  • Shortest Common Supersequence | Finding all SCS
  • Longest Increasing Subsequence using Dynamic Programming
  • Increasing Subsequence with Maximum Sum
  • The Levenshtein distance (Edit distance) problem
  • Find size of largest square sub-matrix of 1’s present in given binary matrix
  • Matrix Chain Multiplication
  • Find the minimum cost to reach last cell of the matrix from its first cell
  • Find longest sequence formed by adjacent numbers in the matrix
  • Count number of paths in a matrix with given cost to reach destination cell
  • 0-1 Knapsack problem
  • Partition problem
  • Subset sum problem
  • Minimum Sum Partition problem
  • Find all N-digit binary strings without any consecutive 1’s
  • Rod Cutting
  • Maximum Product Rod Cutting
  • Coin change-making problem (unlimited supply of coins)
  • Coin Change Problem (Total number of ways to get the denomination of coins)
  • Longest alternating subsequence
  • Count number of times a pattern appears in given string as a subsequence
  • Collect maximum points in a matrix by satisfying given constraints
  • Find optimal cost to construct Binary Search Tree
  • Word Break Problem
  • Wildcard Pattern Matching
  • Total possible solutions to linear equation of k variables
  • Pots of Gold Game using Dynamic Programming
  • Find minimum cuts needed for palindromic partition of a string
  • Maximum Length Snake Sequence
  • 3 Partition Problem
  • Check if given string is interleaving of two other given strings
  •  

    Programming puzzles –

     

    Misc –




     
     

    Thank you for being with us. 🙂

     




    Leave a Reply

    Notify of
    avatar
    wpDiscuz