Meeting #10: Recursion

Recursion

Recursion is a method of solving problems, where functions call themselves to do repeated actions on data that is passed through parameters. This is a hard concept to grasp at first, but it will get easier as you get more practice.

When attempting to solve a problem with recursion, we need to get into a recursive mindset. First, we need to determine what we are going to do every time we call the function. This is typically something that we have to repeat on every iteration. The function is then going to call to itself until it reaches something called a base case, which is when the end result has been reached.

How can we print the Fibonacci sequence using a recursive approach?

Remember that to calculate for a value for the Fibonacci sequence, you must get the sum of the previous two numbers of the sequence. So the sequence would start at one, and continue on (0, 1, 1, 2, 3, 5, 8, 11, …)

Coming back to our recursive mindset, you can note that the repetitive task we have to do is get the previous two numbers. We can continuously call our function to get the value of the previous two numbers. We then must specify the base case, which is when the recursion stops and starts returning the value. In this case, our base case occurs when our current index is either 1 or 0 (end of the sequence).

The code is below:

#include <bits/stdc++.h>
using namespace std;

int recursion(int index) { // recursion function
if (index == 0) return 0; // base case
if (index == 1) return 1; // base case
return recursion(index-1) + recursion(index-2); // call itself to get the sum of the last two indexes
}

int main() {
cout << "Which index of the Fibonacci sequence do you want to calculate?" << endl;
int ind;
cin >> ind;
cout << recursion(ind) << endl;
return 0;
}

Let’s go with a more complicated example.

Andrew steals things. He recently noticed that a house on his street has an open window at all times. Inside the house, there are only ten items to steal. Each day, he can only steal one item from the house to prevent getting caught. What are all the possible ways he could steal the items (order of them)?

#include <bits/stdc++.h>
using namespace std;

void recursion(int days, vector<string> items_stolen, vector<string> items_to_steal) {
if (itemsToSteal.empty()) { // no more items left to steal (base case)
for (int i = 0; i < items_stolen.size(); i++) {
cout << items_stolen[i] << " "; // print item order
}
cout << endl;
return; // leave function since we're done
}

for (int i = 0; i < items_to_steal.size(); i++) {
vector<string> items_stolen_copy = items_stolen; // copy vector
vector<string> items_to_steal_copy = items_to_steal; // copy vector
items_stolen_copy.push_back(items_to_steal[i]); // add new stolen item to vector
items_to_steal_copy.erase(items_to_steal_copy.begin()+i); // delete stolen item from vector

recursion(days-1, items_stolen_copy, items_to_steal_copy); // call recursive function
}
}

int main() {
// test the program
vector<string> items_to_steal = {"dog", "cat", "tv", "laptop", "baby", "chair", "books", "table", "juice box", "seshan"}; // steal these items
recursion(10, vector<string>(), items_to_steal); // call recursive function
}

Note: this is not the fastest way to solve the problem, but is a good example of using recursion.

In this case, our base case is when there are no items left for Andrew to steal. We then print the order of the items stolen when we reach this point. Otherwise, we call the recursion function several times with all of the possible items Andrew could steal on that day.

Recursion takes time to get used to… But with practice, you will be able to master it!

Challenge!

https://dmoj.ca/problem/bf1easy

https://dmoj.ca/problem/bts17p2

Challenge: https://dmoj.ca/problem/ecoo18r1p4

Challenge: https://dmoj.ca/problem/ccc18j5