Lesson Plan

Problems on

Recursion
Today’s Checklist:

Some important Problems on Recursion

Q. Tower of Hanoi

The tower of Hanoi is a famous puzzle where we have three rods and N disks. The objective of the puzzle is to

move the entire stack to another rod. You are given the number of discs N. Initially, these discs are in rod 1. You

need to print all the steps of disc movement so that all the discs reach the 3rd rod. Also, you need to find the

total moves.

Note: The discs are arranged such that the top disc is numbered 1 and the bottom-most disc is numbered N.

Also, all the discs have different sizes and a bigger disc cannot be put on the top of a smaller disc..

Input: 2

Output: 3

Disk 1 moved from A to B

Disk 2 moved from A to C

Disk 1 moved from B to C

Explanation: For N=2, steps will be as follows in the example and a total of 3 steps will be taken.

Input: 3

Output: 7

Disk 1 moved from A to C

Disk 2 moved from A to B

Disk 1 moved from C to B

Disk 3 moved from A to C

Disk 1 moved from B to A

Disk 2 moved from B to C

Disk 1 moved from A to C

Explanation: For N=3 , steps will be as follows in the example and a total of 7 steps will be taken.

Java
C++ &+ DSA
DSA
Code:

long toh(int N, int from, int to, int aux) {

long moves = 0L;

if (N >= 1) {

// Recursive call to move top disk from "from" to aux

in the current call

moves += toh(N - 1, from, aux, to);

cout << "move disk " << N << " from rod " << from <<
" to rod " << to << endl;

// Increment moves

moves++;

// Recursive call to move top disk from aux to "to"

in the current call

moves += toh(N - 1, aux, to, from);

return moves;

Code Explanation:

The idea is to use the helper node to reach the destination using recursion. Below is the pattern for this problem:

Shift ‘N-1’ disks from ‘A’ to ‘B’, using C

Shift the last disk from ‘A’ to ‘C’

Shift ‘N-1’ disks from ‘B’ to ‘C’, using A.

Steps 1 and 3 are actually the same as the original problem. Thus we have derived a recursive solution for the

given problem.

//base case N=1 then simply move the disk from the source rod to the destination rod.

Create a function toh where pass the N (current number of disk), srcRod, destRod, helperRod

Now Making function call for N – 1 disk. (move them from src to helperRod

Then we are printing the current disk along with srcRod and destRo

Again making a fucntion call for N – 1 disk (move them from helperRod to srcROD).

Time complexity: O(2^N), As each function call calls itself two times by decreasing N just by 1.

Auxiliary Space: O(N), As at an instant we will have at most N function calls in the stack.

Q. Array Traversal using recursion

Code:

void traverseArray(int arr[], int idx, int length) {

// Base case: Exit when index goes beyond array length

if (idx >= length) {

return;

Java
C++ &+ DSA
DSA
 }

// Print current element

cout << arr[idx] << " ";

// Recursive call for the next index

traverseArray(arr, idx + 1, length);

Code Explanation:

We are passing the array and current index as input and for each index

We print the curr element the call function for the next index and here the base will be when the index goes out

of bound i.e index>=arr.length

Time Complexity: O(n) , visiting each element of array once

Space Complexity: O(n), Stack space grows linearly with array size due to recursion.

Q. Max element of Array using recursion

Input: arr[] = {10, 20, 4}

Output: 20

Explanation: Among 10 20 and 4, 20 is the largest.

Input: arr[] = {20, 10, 20, 4, 100}

Output: 100 //cleary 100 is largest

Code:

int largest(int arr[], int n, int i) {

// Last index returns the element

if (i == n - 1) {

return arr[i];

// Find the maximum from the rest of the array

int recMax = largest(arr, n, i + 1);

// Compare with i-th element and return

return max(recMax, arr[i]);

Code Explanation:

Set an integer i = 0 to denote the current index being searched

Check if i is the last index, return arr[i]

Increment i and call the recursive function for the new value of i

Compare the maximum value returned from the recursion function with arr[i]

Return the max between these two from the current recursion call.

C
Java &
++ + DSA
DSA
Time complexity: O(N), as for each index we are calling function only one (i.e for the next index), there will total
of n such calls 1 for each index

Auxiliary Space: O(N), since this will size the recursion stack, as function calls get piled up

Q. Remove all occurrences of a character in a string

Input : s = "banana"

c = 'a'

Output : s = "bnn" ,removed all ‘a’

Code:

string removeChar(string str, char ch) {

// Base Case

if (str.length() == 0) {

return "";

// Check the first character of the given string if it's ch

then remove it

if (str[0] == ch) {

// Pass the rest of the string to the recursive function

call

return removeChar(str.substr(1), ch);

// Add the first character since if it's not ch, if we

reached here

return str[0] + removeChar(str.substr(1), ch);

Code Explanation:
Here our recursive function’s base case will be when string length becomes 0.
And in the recursive function, if the encountered character is the character that we have to remove then call
the recursive function from the next character
else store this character in answer and then call the recursive function from the next character.
Time Complexity: O(n), as for each index we are making the function call once.  

Auxiliary Space: O(n), if we consider recursion stack space

Q. Given an integer array nums of unique elements, return all possible subsets(the power set).(Leetcode 78)

Input: nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

C++ &+ DSA

Java DSA
Code:

void recSubsets(int i, vector<int>& nums, vector<int>&

prevSubSet, vector<vector<int>>& tring removeChar(string str,
char ch) {

// Base Case

if (str.length() == 0) {

return "";

// Check the first character of the given string if it's ch

then remove it

if (str[0] == ch) {

// Pass the rest of the string to the recursive function

call

return removeChar(str.substr(1), ch);

// Add the first character since if it's not ch, if we

reached here

return str[0] + removeChar(str.substr(1), ch);

Code Explanation:

We are solving the problem using resSubsets() function, which takes the following inputs, i curr index of
elements in nums, the nums array of elements, prevSubset which has subset form up to this index, and then last
we have the res array which will store the final result

Base case: so in rec function call base case if if each completes the array i.e i==n then we’ll put push our
subset formed (i.e prevSubset) to the res

Now for each index, we have two choices either we include the curr char or we exclude it thus we form a new
extraSubset array in which we include the curr element of array

Now we make two function calls for the next element one including curr element (i.e with prevSubset) and
one excluding curr element (i.e with extra subset)

At last we return this res array which will have all the subset

Time Complexity: O(2^n), for each char in the string we make 2 calls

Space Complexity: O(n), due to recursive stack

Q. Print subsets of a string containing duplicate characters.

Input: aaa

Output: a, a, a, aa, aa, aa, aaa

Java
C++ &+ DSA
DSA
Code:

vector<string> al; // Global vector to store subsequences

void findSubsequences(string s, string ans) {

if (s.length() == 0) {

al.push_back(ans);

return;

// Adding 1st character in the string

findSubsequences(s.substr(1), ans + s[0]);

// Not adding first character of the string

findSubsequences(s.substr(1), ans);

Code Explanation:

In each recursive function call, we are making two calls when moving to the next one selecting the curr char

and one not selectin curr char

The base case when the string has nothing left we can thus add generated string to array and return
For other case make two calls first one while adding curr character to string and the other one without
adding it

Thus on running this function all the generated substrings will be pushed to global array of string i.e al
Time Complexity: O(2^n),for each char in string we make 2 calls

Space Complexity: O(n), due to recursive stack

Q. Print all increasing sequences of length k from first n natural numbers

Input: k = 2, n = 3

Output: 1 2

1 3

2 3

Input: k = 5, n = 5

Output: 1 2 3 4 5

Code:

void printArr(int arr[], int k) {

for (int i = 0; i < k; i++)

cout << arr[i] << " ";

cout << "\n";

Java
C++ &+ DSA
DSA
 void printSeqUtil(int n, int k, int len, int arr[]) {

if (len == k) {

printArr(arr, k);

return;

int i = (len == 0) ? 1 : arr[len - 1] + 1;

len++;

while (i <= n) {

arr[len - 1] = i;

printSeqUtil(n, k, len, arr);

i++;

len--;

void printSeq(int n, int k) {

int arr[k];

int len = 0;

printSeqUtil(n, k, len, arr);

int main() {

int k = 3, n = 7;

printSeq(n, k);

return 0;

Code Explanation:
The idea is to create an array of lengths k. The array stores the current sequence. For every position in the array,
we check the previous element and one by one put all elements greater than the previous element. If there is
no previous element (first position), we put all numbers from 1 to n.

Base Case: if len ==k If the length of the current increasing sequence becomes k, print i
Decide the starting number to put at the current position if len is 0 then it's 1 otherwise it is prev element +1,
as we are adding a new element increase the lengt
In the while loop Put all numbers (which are greater than the previous element) at the new position
Now undo the increase made to len to subtract 1 from it since len is shared among all functions all

Thus all increasing subsequence of length k will be printed

Time Complexity: O(n*n!), as there are n! permutations and it requires O(n) time to print a permutation. T(n) =
n * T(n-1) + O(1) when reduced will result in O(n*n!) time.

Auxiliary Space: O(n), as at any time there will at most n function calls in the stack

Q. Finding all permutations of a string given all elements of the string are unique

Input: S = “ABC”

Output: “ABC”, “ACB”, “BAC”, “BCA”, “CBA”, “CAB”

Java
C++ &+ DSA
DSA
Input: S = “XY”

Output: “XY”, “YX”

Code:

void permute(string str, int l, int r) {

if (l == r)

cout << str << endl;

else {

for (int i = l; i <= r; i++) {

swap(str[l], str[i]);

permute(str, l + 1, r);

swap(str[l], str[i]); // Backtrack to restore the

original string

Code Explanation:
Create a function permute() with parameters as input string, starting index of the string, ending index of the
strin
Call this function with values input string, 0, size of string –
In this function, if the value of L and R is the same then print the same strin
Else run a for loop from L to R and swap the current element in the for loop with the inputString[L
Then again call this same function by increasing the value of L by
After that again swap the previously swapped values to initiate backtracking

Time Complexity: O(N * N!) Note that there are N! permutations and it requires O(N) time to print a
permutation.

Auxiliary Space: O(N) As `l` progresses from 1 to `n-1`, the function generates up to `n` recursive calls until it
reaches the base condition `l == r`. So at any instant, there can be utmost N calls in the call stack.

Q. Given an array, generate all the possible subarrays of the given array using recursion.

Examples:

Input : [1, 2, 3]

Output : [1], [1, 2], [2], [1, 2, 3], [2, 3], [3]

Input : [1, 2]

Output : [1], [1, 2], [2]

Code:

void printSubArrays(vector<int> arr, int start, int end)

// Stop if we have reached the end of the array

if (end = = arr.size())

return;

Java
C++ &+ DSA
DSA
 // Increment the end point and start from 0

else if (start > end)

printSubArrays(arr, 0, end + 1);

// Print the subarray and increment the starting point

else {

cout << "[";

for (int i = start; i < end; i++)

cout << arr[i] << ", ";

cout << arr[end] << "]" << endl;

printSubArrays(arr, start + 1, end);

return;

Explanation: We use two pointers start and end to maintain the starting and ending point of the array and
follow the steps given below:

Stop if we have reached the end of the array

Increment the end index if start has become greater than end

Print the subarray from index start to end and increment the starting index

Time Complexity: 2^n,these many function calls

Auxiliary Space: 2^n, recursion stack

Q. Given a string, write a recursive function that checks if the given string is a palindrome, else, not a
palindrome.

Examples:

Input : malayalam

Output : Yes

Reverse of malayalam is also

malayalam.

Input : max

Output : No

Reverse of max is not max.

Code:

bool isPalRec(char str[], 

int s, int e)

// If there is only one character

if (s = = e)

return true;

Java
C++ &+ DSA
DSA
 // If first and last

// characters do not match

if (str[s] ! = str[e])

return false;

// If there are more than 

// two characters, check if 

// middle substring is also 

// palindrome or not.

if (s < e + 1)

return isPalRec(str, s + 1, e - 1);

return true;

bool isPalindrome(char str[])

int n = strlen(str);

// An empty string is 

// considered as palindrome

if (n = = 0)

return true;

return isPalRec(str, 0, n - 1);

Explanation:

1) If there is only one character in the string return true.

2) Else compare the first and last characters and recur for a remaining substring.

Time Complexity: O(n), n function calls

Auxiliary Space: O(n), recurssive stack

Q. Given two numbers a and b, the task is to find the GCD of the two numbers.

Input: a = 20, b = 28

Output: 4

Explanation: The factors of 20 are 1, 2, 4, 5, 10 and 20. The factors of 28 are 1, 2, 4, 7, 14 and 28. Among these
factors, 1, 2 and 4 are the common factors of both 20 and 28. The greatest among the common factors is 4.

Input: a = 60, b = 36

Output: 12

Java
C++ &+ DSA
DSA
Code:

int gcd(int a, int b)

return b = = 0 ? a : gcd(b, a % b);  

Time Complexity: O(log(min(a,b))

Auxiliary Space: O(log(min(a,b))

Q. Given an integer, K. Generate all binary strings of size k without consecutive 1’s.

Examples:

Input : K = 3  

Output : 000 , 001 , 010 , 100 , 101

Input : K = 4 

Output : 0000 0001 0010 0100 0101 1000 1001 1010

Code:

void generateAllStringsUtil(int K, char str[], int n) {

if (n = = K) {

str[n] = '\0';

cout << str << " ";

return;

if (str[n - 1] = = '1') {

str[n] = '0';

generateAllStringsUtil(K, str, n + 1);

if (str[n - 1] = = '0') {

str[n] = '0';

generateAllStringsUtil(K, str, n + 1);

str[n] = '1';

generateAllStringsUtil(K, str, n + 1);

void generateAllStrings(int K) {

if (K <= 0)

return;

char str[K];

str[0] = '0';

generateAllStringsUtil(K, str, 1);

Java
C++ &+ DSA
DSA
 str[0] = '1';

generateAllStringsUtil(K, str, 1);

Explanation: Idea behind that is IF string ends with ‘1’ then we put only ‘0’ at the end. IF string ends with ‘0’ then
we put both ‘0’ and ‘1’ at the end of string for generating new string.

Time complexity: 2^K where K is the size of the binary string. This is due to the fact that the algorithm
recursively generates all possible binary strings of length K.

Auxiliary space: O(K), since we are using a string array of size K to store the binary string.

Q. Combination Sum (Leetcode 39)

Given an array of distinct integers candidates and a target integer target, return a list of all unique
combinations of candidates where the chosen numbers sum to target. You may return the combinations in any
order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are
unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than
150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7

Output: [[2,2,3],[7]]

Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.

7 is a candidate, and 7 = 7.

These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8

Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1

Output: []

Java
C++ &+ DSA
DSA
Code:

void recursive(vector < int > & candidates, int target, set <
vector < int >> & path, vector < int > & curr) {

if (target = = 0) {

vector < int > temp = curr;

sort(temp.begin(), temp.end());

if (path.count(temp) = = 0)

path.insert(temp);

return;

if (target < 0)

return;

for (int i = 0; i < candidates.size(); ++i) {

curr.push_back(candidates[i]);

recursive(candidates, target - candidates[i], path, curr);

curr.pop_back();

vector < vector < int >> combinationSum(vector < int > &
candidates, int target) {

set < vector < int >> path;

vector < int > curr;

recursive(candidates, target, path, curr);

vector < vector < int >> ans;

for (auto a: path)

ans.push_back(a);

return ans;

Explanation: His code finds unique combinations of numbers from the candidates vector that sum up to the
target using a recursive backtracking approach. It stores unique combinations in a set to avoid duplicates.

Time complexity: Exponential, typically O(2^n) where 'n' is the number of candidates or the depth of recursion.

Space complexity: O(n * m), where 'n' is the number of combinations and 'm' is the average length of
combinations stored in the set.

Q. Generate Parentheses (Leetcode 22)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Java
C++ &+ DSA
DSA
Example 1:
Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:
Input: n = 1

Output: ["()"]

Code:

class Solution {

public:

vector<string> generateParenthesis(int n) {

vector<string> res;

addingpar(res, "", n, 0);

return res;

void addingpar(vector<string> &v, string str, int n, int m){

if(n= =0 && m= =0) {

v.push_back(str);

return;

if(m > 0){ addingpar(v, str+")", n, m-1); }

if(n > 0){ addingpar(v, str+"(", n-1, m+1); }

};

Explanation: The idea is intuitive. Use two integers to count the remaining left parenthesis (n) and the right
parenthesis (m) to be added. At each function call add a left parenthesis if n >0 and add a right parenthesis if
m>0. Append the result and terminate recursive calls when both m and n are zero.

Q. Kth Symbol in Grammar (Leetcode 779)

We build a table of n rows (1-indexed). We start by writing 0 in the 1st row. Now in every subsequent row, we look
at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

For example, for n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.

Given two integer n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.

Example 1:
Input: n = 1, k = 1

Output: 0

Explanation: row 1: 0

Java
C++ &+ DSA
DSA
Example 2:
Input: n = 2, k = 1

Output: 0

Explanation:

row 1: 0

row 2: 01

Example 3:
Input: n = 2, k = 2

Output: 1

Explanation:

row 1: 0

row 2: 01

Code:

int kthGrammar(int N, int K) {

if (N = = 1 && K = = 1)

return 0;

if (K <= pow(2, N-2))

return kthGrammar(N-1, K);

else

return !kthGrammar(N-1, K-pow(2, N-2));

Explanation: This function determines the value (0 or 1) at position K in the sequence based on the kth
grammar sequence, where each subsequent row is derived from the previous row following a specific pattern.

Time complexity: O(log N) - The function divides the problem in half recursively by approximately half with
each step.

Space complexity: O(log N) - The space used on the call stack due to the recursive function calls, proportional
to the height of the recursion tree (log N).

Q. Count and Say (Leetcode 38)

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

countAndSay(1) = "1"

countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into
a different digit string.

To determine how you "say" a digit string, split it into the minimal number of substrings such that each substring
contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally,
concatenate every said digit.

Java
C++ &+ DSA
DSA
For example, the saying and conversion for digit string "3322251":

Given a positive integer n, return the nth term of the count-and-say sequence.

Example 1:
Input: n = 1

Output: "1"

Explanation: This is the base case.

Example 2:
Input: n = 4

Output: "1211"

Explanation:
countAndSay(1) = "1"

countAndSay(2) = say "1" = one 1 = "11"

countAndSay(3) = say "11" = two 1's = "21"

countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

Code:

string countAndSay(int n, string s = "1") {

if(n = = 1) return s;

int i = 0, j, len = s.size();

string res = "";

while(i < len) {

j = i;

while(i < len && s[i] = = s[j]) i++;

res += to_string(i - j) + s[j];

return countAndSay(n - 1, res);

Explanation: This function creates a sequence by reading the previous sequence and saying out loud the
count of consecutive numbers.

Java
C++ &+ DSA
DSA
It starts with "1" as the initial value.

For each iteration, it reads the previous sequence, counts how many times a digit appears consecutively, and
says that count followed by the digit itself.

This process repeats for 'n' iterations to generate the desired sequence..

Time complexity: O(2^n) - The length of the string doubles with each iteration, performing operations linearly
proportional to the string length for each of the n iterations.

Space complexity: O(2^n) - Space on the call stack due to the recursive calls, proportional to the number of
iterations (n) and the length of the string generated at each step.

Q. Permutation Sequence (Leetcode 60)

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"

"132"

"213"

"231"

"312"

"321"

Given n and k, return the kth permutation sequence.

Example 1:
Input: n = 3, k = 3

Output: "213"

Example 2:
Input: n = 4, k = 9

Output: "2314"

Example 3:
Input: n = 3, k = 1

Output: "123"

Code:

class Solution {

public:

string getPermutation(int n, int k) {

int fact = 1;

vector<int> numbers;

for(int i=1;i<n;i++){

// To find (n-1)!

Java
C++ &+ DSA
DSA
 fact = fact*i;

numbers.push_back(i);

numbers.push_back(n);

string ans="";

k = k-1;

while(true){

//Add the first element of reqd permutation

ans = ans + to_string(numbers[k/fact]);

//Erase that element from vector 

numbers.erase(numbers.begin() + k/fact);

if(numbers.size()==0) break;

//Find the position for remaining elements

k = k%fact;

//Find the reqd factorial

fact = fact/numbers.size();

return ans;

};

Explanation: Just keep fixing the position of element by finding their relevant group. Then remove that fixed
element from the data strucuture i.e. vector. Check for remaining elements until vector is empty.

Time complexity: O(n^2), Due to the erasing operation within the loop

Space complexity: O(n), Utilizes a vector of size 'n' to store numbers.

Java
C++ &+ DSA
DSA
THANK

YOU !