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 –

Print all possible solutions to N Queens problem

Print all Possible Knight’s Tours in a chessboard

Find Shortest Path in Maze

Find Longest Possible Route in a Matrix

Find path from source to destination in a matrix that satisfies given constraints

Find total number of unique paths in a maze from source to destination

Print All Hamiltonian Path present in a graph

Print all k-colorable configurations of the graph (Vertex coloring of graph)

K-Partition Problem | Printing all Partitions

Find ways to calculate a target from elements of specified array

Determine if a pattern matches with a string or not

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

Check if a string is K-Palindrome or not

Break a string into all possible combinations of non-overlapping substrings

Determine if a pattern matches with a string or not

Remove adjacent duplicate characters from a string

Print all combinations of phrases that can be formed by picking words from each of given lists

Find all N-digit numbers with equal sum of digits at even and odd index

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

Add elements of two arrays into a new array

Find ways to calculate a target from elements of specified array

Print all combination of numbers from 1 to n having sum n

Print all combinations of positive integers in increasing order that sum to a given number

Find all distinct combinations of given length

Matrix –

Find all occurrences of given string in a character matrix

Flood Fill Algorithm

Print Matrix in Spiral Order

Find all paths from first cell to last cell of a matrix

Replace all occurrences of 0 that are not surrounded by 1 in a binary matrix

Find probability that a person is alive after taking N steps on the island

Divide & Conquer –

Exponential search

Find number of rotations in a circularly sorted array

Find smallest missing element from a sorted array

Find number of 1’s in a sorted binary array

Find the peak element in an array

Maximum Sum Subarray using Divide & Conquer

Efficiently implement power function | Recursive and Iterative

Find Floor and Ceil of a number in a sorted array (Recursive solution)

Find Minimum and Maximum element in an array by doing minimum comparisons

Find Frequency of each element in a sorted array containing duplicates

Linked List –

Split linked list into two lists where each list containing alternating elements from it

Construct a linked list by merging alternate nodes of two given lists

Merge given sorted linked lists into one

Merge Sort for Singly Linked List

Reverse linked list | Part 2 (Recursive Solution)

Merge alternate nodes of two linked lists into the first list

Check if linked list is palindrome or not

Move last node to front in a given Linked List

Rearrange a Linked List by Separating Odd nodes from the Even Ones

Calculate height of a binary tree with leaf nodes forming a circular doubly linked list

Sorting –

Insertion sort | Iterative & Recursive

Selection sort | Iterative & Recursive

Bubble sort | Iterative & Recursive

Merge Sort Algorithm

Inversion Count of an array

Quicksort Algorithm

Hybrid QuickSort

Quicksort using Dutch National Flag Algorithm

Quick Sort using Hoare’s Partitioning scheme

Find all distinct combinations of given length

Heap –

Heap Sort (Out-of-place and In-place implementation)

Check if given array represents min heap or not

Convert Max Heap to Min Heap in linear time

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

Find all nodes at given distance from leaf nodes in a binary tree

Find maximum sum path between two leaves in a binary tree

Fix a binary tree that is only one swap away from becoming a BST

Count all subtrees having same value of nodes in a binary tree

Calculate height of a binary tree with leaf nodes forming a circular doubly linked list

Find Maximum Difference Between a Node and its Descendants in a Binary Tree

C++ Program to Print Binary Tree Structure

Binary Search Tree –

Insertion in BST

Search given key in BST

Deletion from BST

Construct balanced BST from given keys

Determine if given Binary Tree is a BST or not

Check if given keys represents same BSTs or not without building the BST

Find inorder predecessor for given key in a BST

Find Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree

Find K’th smallest and K’th largest element in BST

Floor and Ceil in a Binary Search Tree

Convert a Binary Tree to BST by maintaining its original structure

Remove nodes from BST that have keys outside the valid range

Find a pair with given sum in a BST

Fix a binary tree that is only one swap away from becoming a BST

Update every key in BST to contain sum of all greater keys

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

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 –

Generate power set of a given set

Implement power function without using multiplication and division operators

Multiply two numbers without using multiplication operator or loops

Print all numbers between 1 to N without using any loop | 4 methods

Tower of Hanoi Problem

Print all numbers between 1 to N without using semicolon

Find ways to calculate a target from elements of specified array

Check if a string is K-Palindrome or not

Graphs –

Breadth First Search (BFS) | Iterative & Recursive Implementation

Depth First Search (DFS) | Iterative & Recursive Implementation

Disjoint-Set Data Structure (Union Find Algorithm)

Misc –

Traverse the given directory using BFS and DFS in Java

C++ Implementation of Trie Data Structure

Thank you for being with us. 🙂

Leave a Reply

Subscribe

newest oldest most voted

Guest

Rahul Padhy

Share On Twitter Share On Google

Hey, great work guys.. But it would be better if we can have more questions that focus on exhaustive recursion.. For example, the naive approach to the Painter’s Partition Problem or this question, for instance :
Given a pattern string like “ABBA” and an input string like “redbluebluered”, return true if and only if there’s a one to one mapping of letters in the pattern to substrings of the input.