Recursion and Friends

Using an Algo Question to explain it

So earlier this week I’ve attended multiple different Algo Clubs and tutorials. One of which taught me about recursion and similar patters that go along with them.

The problem we went over was

Given a number n, count minimum steps to minimize it to 1 according to the following criteria:

If n is divisble by 2 then we may reduce n to n/2
If n is divisble by 3 then we may reduce n to n/3
Or decrement n by 1

On my first attempt I want for the greedy approach since I’m not typically comfortable in creating recursion. Which looked like

While this looked like it should get me the correct answer, my answer was always greater than the answer of the out. The reason being is that for greater numbers it makes sense to attempt to keep dividing by 3 as much as possible instead of 2. However, the answer varies a lot. So then I took my first attempt at recursion.

Just in case you didn’t know, recursion is when you call upon your function inside of your function. Allowing it to descend or increase according to what you need.

This was the attempt that I had with my recursion. The risk this had was that there are recursion limits set by different languages. Because I’m checking every single possible way during the recursion, I can potentially hit the limit really quickly as the number grows.

This Is Where Memoization Comes In

Memoization is a technique used to help speed up programs by storing or caching expensive function calls. To simplify it, we are building a list of all our calls and making it easier to traverse since we immediately return an answer once we’ve gone over it.

During memoization we start storing our data into a cache. If our answer is in there then we can immediately just return it. IF this function was going to be called multiple times in different moments we can move the cache to outside of the function so that we have a global cache that we can always store our answers making our function significantly faster the more numbers we give it.

Now to Introduce Tabulation

Tabulation is a systematic and logical representation of numeric data in rows and columns to facilitate comparison and statistical analysis. In simpler terms it organizes the data into a tabular form. This last one was introduced to us as another way we can go about

You can see it work here, as we traverse to solve our problem it stores it in the index for the answer and as we continue to increase we are able to get further up to the answer quicker and quicker. This is comparable to memoization in many ways, but categorizes within an array not an object.

These are some lite examples of how to solve difficult problems using more advanced methods. Try them out and see how they work for you. You’ll notice that your code can get significantly faster as it continues.

-Happy Coding

Jump into the code