This tutorial will cover explicit use of recursion and its implementation in problems. This topic is not used directly to solve problems in contests but rather is an essential tool in Dynamic Programming, Tree algorithms, Graph Traversal, etc. Topics like time complexity and space complexity of recursive function are not discussed in this tutorial.
What is recursion?
When a function calls itself, then its called recursion. That is the most basic definition. This definition is enough when you need to solve basic problems like fibonacci series, factorial, etc. This is the implicit use of recursion.
Problems like printing all permutations, combination or subsets uses explicit use of recursion also known as "Complete Search".
Approach to solve a problem recursively
When solving a problem through recursion one must think of breaking the current problem into sub-problem. Sub-problem is chosen such that we can keep on breaking the sub-problems until we reach a sub-problem whose answer is already known. We can take example of fibonacci series to explain this, fibonacci series is defined as f(n) = f(n-1) + f(n-2); while f(1) = 1 & f(0) = 0, we can keep on calling f(n-1) and f(n-2) until we reach either 1 or 0, whose answers we already know. This is a sub-problem.
This is rather the easier part of a recursive solution. After finding a suitable sub-problem we need a recurrence relation and a base case. In the above example, the definition of fibonacci series acts as recurrence relation and f(1) and f(0) as base cases for us. But finding the recurrence relation is the most difficult part.
A problem can have more than one sub-problem. One type of sub-problem can be used in multiple questions. Think of the problem which is more intuitive to you and you can break it until you find a suitable base case. I will discuss three problems here (1 easy and 2 medium level problems and will be using leetcode problems).
Problem 1:
Explanation:
We can say that we have an integer N. We can choose to either decrease it by 1 or by 2. Now we can say that we have two new problems N-1 and N-2. If we know the answer to this problem we can find the answer for N. We can further decrease N-1 by either 1 or by 2 and we can do the same with N-2. We can keep on decreasing the integer until we either reach 0 or a negative number. This is quite hard to visualize so I prefer to imagine a recursive tree while thinking of a recursive solution.
3
/ \
/ \
2 1
/ \ / \
/ \ / \
1 0 0 -1
/ \
/ \
/ \
0 -1
We take N=3 and now 3 is once decreased to 2 and once to 1 and then they keep on decreasing further until we either reach 0 or -1 that are our base cases
Now we can say that the elements of branches which reached 0 are our solution and the branches which reached negative integers are to be discarded.
However, this solution alone would give TLE and requires memoization to get accepted, but this gives a good idea of how to think of a recursive solution where its not clearly obvious to see recursion would work.
int climb(int n, vector<int> &a) {
int ans = 0;
if (n == 0)
return 1;
if (n < 0)
return 0;
if (a[n - 1] != -1)
return a[n - 1];
ans += climb(n - 1, a);
ans += climb(n - 2, a);
a[n - 1] = ans;
return ans;
}
Problem 2:
Explanation:
In our solution N represents the number on which we will take the decision and K represents the number of elements that we need to include in a combination.
We can start with the number N and we can make a very intuitive decision to either include it in a particular combination or not. If we include an element in a combination we decrease the number 'K' by 1 (means we need 1 less element for the combination) and if we exclude it then we don't change 'K' as we still need K elements for the combination. After that we further make decision on the number n-1. This is a general idea originated from the combinatorics formula: nCr = n-1Cr + n-1Cr-1.
We can keep repeating this process until we either reach (n = 0 && k > 0) (in this case we can just return a 2D vector without any vectors, meaning just discarding this branch as we ran out of elements but our combination isn't formed) or we can reach k = 0 (n can be 0 or not) then we just add the elements of this branch to our answer.
3, 2
/ \
/ \
2, 1 2, 2
/ \ / \
/ \ / \
1, 0 1, 1 1, 1 1, 2
/ \ We can prune here
/ \
0, 0 0, 1
We start with N=3, K=2. When we include 3 in a combination we decrease K by 1, when we didn't include it K remains same. We keep on repeating this process until either K hit 0 (this means we have a valid combination) or N hit 0 (this means we ran out of data before reaching a valid combination). N and K can hit 0 at the same time as well which means last element of provided numbers is also last element of our combination.
This solution alone would give TLE as well. So we can optimize our solution. Whenever we reach a condition where k < remaining elements in the branch then we say that the particular branch will never return a suitable answer. As elements that needs to be added (k) are less than elements that can be added. So we can just return from such conditions. This particular optimization is called PRUNING the solution. It basically means whenever we reach a condition before our base case that we know will not yield a correct answer then we don't traverse in that branch, this saves us a lot of time.
vector<vector<int>> comb(int n, int k, vector<int> v) {
vector<vector<int>> a;
if (n < k - v.size()) // Pruning the solution
return {};
if (n == 0 && v.size() != k)
return {};
if (n == 0 && v.size() == k) {
a.push_back(v);
return a;
}
if (v.size() == k) {
a.push_back(v);
return a;
}
auto s = comb(n - 1, k, v);
v.push_back(n);
auto s1 = comb(n - 1, k, v);
for (int i = 0; i < s.size(); ++i) {
a.push_back(s[i]);
}
for (int i = 0; i < s1.size(); ++i) {
a.push_back(s1[i]);
}
return a;
}
There is another approach possible here, we can segregate our solution and say we need all combinations starting from 1, 2 .... , n. Now when we choose 1 as first element then we need to choose k-1 elements from 2....n, when we choose 2 as first element then we need to choose k-1 elements from 3....n. Pay attention that we are not including 1 here as it would lead to repetitions. Think of it as a challenge and try to solve it using this approach.
Problem 3:
Explanation:
We can fix the first element of the permutation and say that we want to find permutation of N-1 elements. And then we can choose further by saying we fixed second element. We can keep repeating this approach until we fix all elements of the permutation. Till this stage you can imagine what the solution would look like.
[][1, 2, 3]
/ | \
/ | \
[1][2, 3] [2][1, 3] [3][1, 2]
/ \ / \ / \
/ \ / \ / \
/ \ [2, 1, 3][] [2, 3, 1][] / \
/ \ [3, 1, 2][] [3, 2, 1][]
[1, 2, 3][] [1, 3, 2][]
The left array of every node represents current state of our permutation and right array represents remaining elements to be used.
First we start with an empty array say that the first element is either 1, 2 or 3. So we fix the first element, which have three possibilities. Now we can similarly fix second element then all of our previous possibilities are further divided into 2 more possibilities each. On repeating this process we can reach our answer and we stop once our first array have N elements.
void f(vector<int> &nums, int idx, vector<int> perm, vector<vector<int>> &ans) {
int n = nums.size();
if (perm.size() == n) {
ans.push_back(perm);
return;
}
for (int i = 0; i < n; ++i) {
bool rep = false;
for (int j = 0; j < perm.size(); ++j) {
if (perm[j] == nums[(i + idx) % n]) {
rep = true;
break;
}
}
if (rep) {
continue;
}
perm.push_back(nums[(i + idx) % n]);
f(nums, idx + 1, perm, ans);
perm.pop_back();
}
return;
}
Another approach is possible for this problem using a boolean vector and subsequences but that idea is quite unintuitive. But for the information purposes I have mentioned it here.
Note:
The solutions are not fully optimized and can be further optimized using dynamic programming, the aim of this tutorial was to ignite the idea of recursive solutions. ****
Problems for further practice:
Palindrome Partitioning — LeetCode
Partition to K Equal Sum Subsets — LeetCode
