This week, as promised, we have learned the basic concepts of recursion. The general idea was not a novelty for me, since I already had some experience with recursion, but the actual use and application of these concepts were somewhat new to me (and quite interesting).
As with classes and objects, recursion can be foudn in some real world examples. Some of the occurances of recursio can be found in the following pictures:
 |  |  |
These images may be interesting or funny, depending on viewer's point of view, but since this blog is about computer science, we will be looking into application of the recursion concepts in computer science.
In computer science, the most basic definition of example would be a function call from within its own definition.
For example:
def Func(i):
print(i)
Func(i+1)
If this example is confusing, you can imagine what happens step by step: You enter the function at the header with some argument (let's say, i = 1). Then you print it, evaluate i+1, and then... You enter the function at the header with...
As you have probably imagine, this example would create an analogy of an infinite loop and would keep printing numbers from 1 to infinity (or rather until an error occurs).
Of course, we already know how to create infinite loops, and there would be no point in creating the concept if recursion for that. But there are things that can only be achieved with recursion (or at least, it would be preferable, more efficient and easier).
A more useful example of recursion was presented to us on the lectures. Let's say, we wanted to compute a summ of all numbers in a arbitrarily nested list (meaning that this list may contain any number of other list inside, which may also contain other lists, etc.
We already know how to use for loops and add up numbers of the list (or we can use "sum" function to do so). The only problem is that when we try to add a list to a number, python gets really mad. This is where recursion can save the day.
When we were constructing this recursive function, we had to rely on a basic case; or something that we already know how to solve. As I mentioned above, we already know how to add up numbers in a list, using for loop. The concept of recursion comes in handy when we realize that the nested lists are simply smaller problems inside of a big one.
Using this knowledge, we taught our function to reduce the problem to its simpliest case. Our function behaved this way: If the problem is simple (basic case) - solve it and return the result. If the problem is complicated (an entry of a list is another list and not a number) - solve that problem separatelly by calling our function again with only the inner list as an argument. After the inner list was summed up, it is returned to the previous caller (which is the first instance of our function) and then used as a number, representing the sum of numbers in the list. And if the inner list contains another list, same approach would be taken until there are only numbers.
This process can be easily understood from the following example:
lst = [1, 2, [3, 4], 5].
We can't simply add all entries from this list, so we use our function. The first two elements are just numbers, so we can easily sum them up. The third element, though, is another list. In this case, we call our function again, but only on that list.
Now, our function only has to work with
[3, 4]
This case is easy, 3 + 4 is 7, so we return this value. Now, our main list would look like
[1, 2, 7, 5]
Now, it's another simple case: 1 + 2 + 7 + 5 = 15, so we return our value.
You can imagine any list with other lists as elements, so you convert every list into a single number element, starting from the lowest-level list (deepest ones). Until your whole list consists only of numbers, in which case, you simply return the sum.
