Recursion and Iteration

Hey, it's me. For the second time. What better time there is to talk about some problems I have been working on? Recently I am writing simple programs/algorithms but using recursion. You might not know the definition of an iterative and recursive function so I'll try my best to give a simple explanation. A program is iterative when there is some sort of loop (or repetition), and a program is recursive when an entity calls itself or if the function references itself somewhere in the function.

ex:

If we want to write a short program that adds up everything in a list, we might do something like this if we use iteration

In this case, we have a variable "total" that keeps track of the total of the sum. Then we iterate through the entire list, adding the number we iterate onto the "total" variable. Finally, we tell the function to return the total or the sum.

However, if we want to write it recursively...

In a recursive function, things are a bit different. Instead of just going through the entire list directly, we have to think about how to make the problem smaller. What I mean by making the problem smaller is that we want to reach something called a base case, so that the function knows when to return the answer. The base case here is once the list has nothing in it. How are we going to make the list shorter though? Now we have to look at the recursive case. Each time in the recursive case the function is calling itself again, but without the first element of the list.

So something like this:

1. recursive_sum([1,2,3,4,5]

2. recursive_sum([2,3,4,5])

.

.

. recursive_sum([5])

When it finally reaches the end, everything stacks back up and it adds the first element of all of these calls, allowing us to get the sum of a list.

Sure enough, both of these programs evaluate the sum of the list, but the main difference is that in harder problems or algorithms, we might prefer one over another. Before this, I solve the majority of problems I encounter using iteration because it is much more straightforward in my opinion and its the first method I learned. This reminds me of arithmetic and geometric sequences that I learned way back in the day where we have to find the explicit and recursive formulas for the sequences. Something like this

Obviously this is a very simple implementation of iteration and recursion, and there's much much more it can do. If you want to see a much more sophicated explanation of the usage of recursion and iteration, here's a very nice video by Errichto talking about that and dynamic programming in general. My brain still kind of hurts from thinking recursively because it doesn't feel straightforward at all, and I certainly still prefer using iteration, but I think I got the gist of how recursion works after writing a few more problems.

To wrap this post up, I'll talk about some websites I find questions on. The first website I used is codewars, and its the first problem solving website I found, but I no longer use it anymore because the problems there aren't fun. I really like hackerrank and leetcode, since they have many problems dedicated to algorithms and CP problems in general. I feel these two websites are more challenging, but I can't solve any hard questions on it yet. Project Euler is another website that has a ton of questions, and this one is more math orientated, and many of them are insanely hard (I have no idea how to even start). Props to those people who solved almost all of the questions on that website. Amazing people. I guess I'll just have to work my way up there.

I guess this is it for now. Why post this 2am in the morning, you might ask? Because I procrastinated while writing this and my sleep schedule is messed up. Whatever, have a nice day. Good night.

-Rex