Week 7: Recursion!

The main focus of this course so far has been on the recursive technique. Recursion is a computer science technique, where in order to solve a problem it is required to solve smaller instances of the same problem. Recursion involves writing a function whose code includes a reference to the function itself; in other words, it involves functions that call themselves to solve smaller subproblems.

The recursive technique, as we have seen in lecture, often consists of a single return statement, which is usually a list comprehension with two separate parts: the base case and recursive call. A list comprehension allows for the creation of a new list through iteration within a single line, making the code much more concise and understandable. The base case is the instance of the function which does not lead to a recursive call; this is probably one of the most important elements of recursion, as without it, the function would consist of infinite recursion; in other words, the program would cause the function to continuously keep recalling itself until it crashes. On the other hand, the recursive call part of the return statement includes the reference to the function itself, under a specific condition of an if statement.

Among many of the examples of recursion we saw in lecture are methods involving the classes Tree, LinkedList, and Turtle. We have also seen recursion on nested lists, such as the function sum_list, which takes in a nested list of numbers as an argument and returns the sum of all of its elements.

An advantage of utilizing recursion is the fact that sometimes it is the only way of solving certain very complex problems. By breaking a very complex problem into smaller, simpler cases, the problem suddenly becomes much easier to deal with. Moreover, the code can become much more elegant and sometimes even more straightforward through the use of recursion.

On the other hand, a disadvantage of the recursive technique is that when processing an extensive instance of the problem which requires a very large amount of recursive calls, the operation might cause a StackOverflowException leading the program to crash.

Overall, recursion is very useful, but sometimes it should be avoided in particularly simple problems in order to prevent Pythonistas from overcomplicating the code.