Recursion

Recursion is definitely the most important concept that we have seen so far in this course. This feature allows us to implement a function by calling the function in its own implementation. But how is this possible? Well, it's as simple (and as complex) as including some code within the implementation of our function that will indicate the program how to work on some base case, so the recursive step will be executed by means of the base case with the indications that we will give to the code. This might sound a bit confusing, so let's define an example and trace it to see how recursion works.

In class, we've seen the function rec_max(L) which returns the maximum number in a possibly nested list of numbers. This is what it looks like:

As we can see, we are using rec_max() inside the function implementation. This is the recursive step. The base case is the bit of code following the 'else' statement. This tells our program to return the biggest element of a non-nested list considering every element in the list. So, our computer now knows that rec_max() works the same way, but only if the element of the list is a nested list. So if an element in L is a nested list, we will get its maximum separately by using the recursive step.
We will get a non nested list with the maximum of every nested list in L and the maximum of the non nested part of L. Finally, the function will return the maximum of this list comprehension.
And this is how recursion works!

As we can see, we could also implement rec_max() without using recursion by considering every element in L separately using if statements and for loops. But this will make our code much longer and slower. This is why, I can say with confidence that, we should always use recursion when it's possible.